Ngôi Nhà Của Giun

Cho một đồ thị vô hướng $n$ đỉnh (đánh số $1,2,\dots ,n$) và $m$ cạnh. Đồ thị không có cạnh nối một đỉnh với chính nó và giữa hai đỉnh bất kỳ có nhiều nhất một cạnh.

Bạn được cho một chu trình Euler trên đồ thị — một dãy $v_0,v_1,\dots ,v_m$ sao cho $v_0=v_m$ và mỗi cạnh của đồ thị xuất hiện đúng một lần trong dãy $(v_0,v_1),(v_1,v_2),\dots ,(v_{m-1},v_m)$. Đỉnh xuất phát $v_0$ là cố định.

Nhiệm vụ của bạn là tìm một dãy $u_0,u_1,\dots ,u_m$ khác cũng là một chu trình Euler trên cùng đồ thị đó, cùng bắt đầu và kết thúc tại đỉnh $v_0$ (tức $u_0=u_m=v_0$), sao cho dãy $(u_0,u_1,\dots ,u_m)$ lớn hơn hẳn dãy $(v_0,v_1,\dots ,v_m)$ theo thứ tự từ điển, và trong số các dãy thỏa mãn điều đó, hãy chọn dãy nhỏ nhất theo thứ tự từ điển.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $m+1$ số nguyên dương không vượt quá $n$ — đó là dãy $v_0,v_1,\dots ,v_m$ mô tả chu trình Euler ban đầu. Bảo đảm $v_0=v_m$.

Dữ liệu ra

• In ra $m+1$ số nguyên dương mô tả chu trình Euler mới tìm được, số đầu tiên phải bằng số cuối cùng và bằng $v_0$.
• Nếu không tồn tại chu trình Euler nào lớn hơn hẳn chu trình đã cho, in ra dòng No solution.

Ràng buộc

• $3\le n\le 100$
• $3\le m\le 2000$
• Đồ thị không có khuyên và không có cạnh bội (nhưng có thể có đỉnh cô lập).

Ví dụ