Lộ Trình Phân Biệt

Có $n$ phòng và $m$ cổng dịch chuyển một chiều. Mỗi ngày, một người chơi bắt đầu từ phòng $1$ và di chuyển đến phòng $n$, nhưng mỗi cổng dịch chuyển chỉ được dùng tối đa một lần trong toàn bộ trò chơi.

Hãy tìm số lượng người chơi tối đa có thể đi từ phòng $1$ đến phòng $n$ và in ra lộ trình của từng người.

Dữ liệu vào

Dòng đầu gồm hai số nguyên $n$ và $m$.

• $m$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $a$ và $b$: cổng dịch chuyển từ phòng $a$ đến phòng $b$.

Dữ liệu ra

Dòng đầu in số $k$ — số lượng người chơi tối đa.

Với mỗi trong $k$ người chơi, in:

• Một dòng chứa số phòng trên lộ trình $l$.
• Một dòng chứa $l$ số nguyên — lộ trình từ phòng $1$ đến phòng $n$.

Ràng buộc

• $2\le n\le 500$
• $1\le m\le 1000$

Ví dụ