Năm 2036, người cao tuổi chiếm phần lớn dân số châu Âu. Để giúp họ duy trì sức khỏe, cơ quan phụ trách nhóm dân số này đề xuất giao cho họ việc phát lượng thư giấy ít ỏi còn được gửi, chủ yếu cũng dành cho người cao tuổi. Đề xuất sẽ được triển khai trên toàn châu Âu.

Châu Âu được chia thành các khu vực bưu chính. Mỗi khu vực có một mạng lưới gồm các con đường và giao lộ; mỗi con đường đều đi được theo hai chiều. Có thể thuê bao nhiêu người đưa thư trong mỗi khu vực tùy ý. Mỗi sáng, một người đưa thư nhận một túi thư để phát theo một hành trình đi qua một phần của mạng lưới.

Mỗi hành trình phải phù hợp với người cao tuổi, nghĩa là:

• Bắt đầu và kết thúc tại cùng một giao lộ.
• Không đi qua một giao lộ nhiều lần, ngoại trừ việc quay lại giao lộ xuất phát để kết thúc hành trình, nhằm tránh gây nhầm lẫn.
• Không có con đường chung với hành trình của người khác.

Các hành trình phải phủ toàn bộ mạng lưới: mỗi con đường thuộc đúng một hành trình.

Hãy tìm một tập hành trình thỏa mãn các điều kiện trên cho mạng lưới đường phố đã cho.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N,M\), lần lượt là số giao lộ và số con đường. Các giao lộ được đánh số từ \(1\) đến \(N\).

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(u,v\), cho biết có một con đường nối giao lộ \(u\) với giao lộ \(v\).

Dữ liệu luôn thỏa mãn:

• \(1 \le u,v \le N\) và \(u \ne v\).
• Giữa hai giao lộ bất kỳ có nhiều nhất một con đường.
• Có thể đi từ giao lộ bất kỳ đến mọi giao lộ khác qua các con đường.
• Tồn tại một tập hành trình phù hợp với người cao tuổi phủ toàn bộ mạng lưới.

Dữ liệu ra

Mỗi dòng mô tả một hành trình bằng dãy số hiệu các giao lộ theo thứ tự người đưa thư đi qua. Giao lộ xuất phát, cũng là giao lộ kết thúc, được in đầu tiên và chỉ in đúng một lần. Sau giao lộ cuối cùng được in, người đưa thư quay về giao lộ đầu tiên.

Nếu có nhiều đáp án, có thể in bất kỳ đáp án hợp lệ nào.

Ràng buộc

• \(3 \le N \le 500\,000\).
• \(3 \le M \le 500\,000\).
• Mạng lưới thỏa mãn tất cả điều kiện đã nêu trong phần dữ liệu vào.

Phân nhóm

1. 38 điểm: \(3 \le N \le 2000\), \(3 \le M \le 100\,000\).
2. 17 điểm: \(3 \le N \le 100\,000\), \(3 \le M \le 100\,000\).
3. 45 điểm: \(3 \le N \le 500\,000\), \(3 \le M \le 500\,000\).

Ví dụ

10 15
1 3
5 1
2 3
9 2
3 4
6 3
4 5
7 4
4 8
5 7
8 5
6 7
7 8
8 10
10 9

2 3 4 5 8 10 9
7 8 4
1 5 7 6 3