Cuộc cãi vã

Thành phố có $n$ ngã tư và $m$ con đường hai chiều nối chúng, mỗi con đường có độ dài bằng nhau. Không có đường nối một ngã tư với chính nó, và giữa hai ngã tư có nhiều nhất một con đường.

Bob sống ở ngã tư số $1$, Alex sống ở ngã tư số $n$. Hôm nay Bob cần đi từ nhà mình tới ngã tư $n$, còn Alex cần đi từ nhà mình tới ngã tư $1$. Hai người vừa cãi nhau nên không muốn gặp nhau ở bất kỳ ngã tư nào cùng một thời điểm.

Hai người xuất phát cùng lúc và di chuyển với vận tốc bằng nhau: trong mỗi bước, mỗi người đi hết đúng một con đường sang ngã tư kề. Cho tới khi cả hai đến đích, không ai được đứng yên, cả hai luôn đi đồng thời trong mỗi bước.

Điều kiện duy nhất là: tại mọi thời điểm (kể cả lúc xuất phát và lúc kết thúc), hai người không được đứng ở cùng một ngã tư. Họ được phép gặp nhau ở giữa một con đường khi đi ngược chiều nhau trên cùng con đường đó. Cũng có thể một người vừa bước vào một ngã tư đúng lúc người kia rời khỏi ngã tư đó (ví dụ Alex đi từ ngã tư $1$ sang ngã tư $2$ trong khi Bob đi từ ngã tư $2$ sang ngã tư $3$).

Hai lộ trình phải có số con đường bằng nhau. Hãy tìm lộ trình cho Bob và Alex sao cho họ không bao giờ ở cùng một ngã tư tại cùng thời điểm, và trong tất cả các cách hợp lệ, chọn cách có số con đường ít nhất. Nếu không tồn tại lộ trình thỏa mãn, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số ngã tư và số con đường.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên là hai ngã tư được nối bởi một con đường.

Dữ liệu ra

Nếu không tồn tại lộ trình thỏa mãn, in ra $-1$.

Ngược lại:

• Dòng đầu in số nguyên $k$: độ dài (số con đường) của lộ trình ngắn nhất.
• Dòng thứ hai in $k+1$ số nguyên: lộ trình của Bob, tức dãy $k+1$ ngã tư mà Bob đi qua (bắt đầu ở $1$, kết thúc ở $n$).
• Dòng thứ ba in $k+1$ số nguyên: lộ trình của Alex theo cùng định dạng (bắt đầu ở $n$, kết thúc ở $1$).

Nếu có nhiều đáp án tối ưu, in ra bất kỳ đáp án nào.

Ràng buộc

• $2\le n\le 500$
• $1\le m\le 10000$
• Không có đường nối một ngã tư với chính nó, không có hai con đường nối cùng một cặp ngã tư.

Ví dụ