Có \(2N\) người và một đồ thị bạn bè hai phía. Mỗi người đến dự tiệc cùng đúng một người bạn, nhưng các cặp đó đã bị quên; đề bảo đảm có đúng một cách chia tất cả mọi người thành \(N\) cặp bạn bè như vậy. Khi một người biết câu chuyện và người đi cùng họ chưa biết, họ bắt buộc truyền cho người đi cùng trước. Nếu không, họ có thể truyền cho một người bạn khác chưa biết; mỗi người chỉ truyền một lần. Hãy tìm số người lớn nhất có thể nghe câu chuyện và in một thứ tự truyền đạt đạt được số đó.

Dữ liệu vào

Dòng đầu chứa \(N,M\) (\(1\le N\le5\cdot10^5\), \(N\le M\le10^6\)). \(M\) dòng tiếp theo chứa cạnh bạn bè \(u_i,v_i\) (\(1\le u_i,v_i\le2N\), \(u_i\ne v_i\)). Đồ thị có thể chia thành hai nhóm sao cho mỗi cạnh nối hai nhóm khác nhau.

Dữ liệu ra

Dòng đầu in \(K\), số người lớn nhất có thể nghe câu chuyện. Dòng hai in \(K\) số \(a_1,\ldots,a_K\) sao cho kể câu chuyện cho \(a_1\) thì mỗi \(a_i\) có thể truyền cho \(a_{i+1}\). Nếu có nhiều dãy tối ưu, in một dãy bất kỳ.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(24\) điểm: \(N\le10\).
2. \(16\) điểm: mỗi người có nhiều nhất hai người bạn.
3. \(30\) điểm: \(N\le2000\), \(M\le5000\).
4. \(40\) điểm: không có ràng buộc thêm.

Ví dụ

2 3
1 2
1 4
3 4

4
2 1 4 3

3 5
1 2
2 3
1 4
4 5
2 5

4
6 1 2 3

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

6
6 3 4 1 2 5

Nguồn

COCI 2025/2026 - Vòng 3, bài Domjenak.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.