Ông Malnar đang tổ chức một buổi tiệc cho ~2N~ cộng sự, được đánh số từ ~1~ tới ~2N~. Các cộng sự tới dự tiệc theo từng cặp. Quan sát hành vi của họ, ông nhận ra một vài quy tắc kỳ lạ chi phối cách thông tin lan truyền trong nhóm này.

Quy tắc thứ nhất: người ~A~ sẵn sàng kể một thông tin cho người ~B~ khi và chỉ khi ~A~ và ~B~ là bạn bè. Hai cộng sự đi cùng nhau tới buổi tiệc chắc chắn là bạn bè.

Quy tắc thứ hai: mỗi người chỉ sẵn sàng truyền một thông tin cho nhiều nhất ~1~ người khác. Đồng thời, người được nhận thông tin đó phải là người chưa biết thông tin.

Quy tắc thứ ba: khi có thể truyền thông tin, mỗi người luôn ưu tiên truyền cho người đã đi cùng mình tới buổi tiệc. Nói cách khác, nếu ~A~ đi cùng ~B~, và ~A~ biết một thông tin mà ~B~ chưa biết, thì ~A~ sẽ kể cho ~B~. Do các quy tắc trước đó, ~A~ sẽ không kể cùng thông tin ấy cho ai khác nữa; còn ~B~ sau khi nghe xong sẽ tiếp tục cố kể cho một người bạn khác của mình, và cứ thế tiếp diễn.

Quy tắc thứ tư: tập người tham dự có thể được chia thành hai nhóm sao cho hai người bạn bất kỳ luôn nằm ở hai nhóm khác nhau.

Ông Malnar sẽ kể câu chuyện của mình cho đúng ~1~ cộng sự đầu tiên. Ông muốn biết nhiều nhất có thể bao nhiêu cộng sự sẽ nghe được câu chuyện. Nếu con số đó là ~K~, ông còn muốn tìm một dãy ~a_1, a_2, \ldots, a_K~ sao cho nếu ông kể câu chuyện cho ~a_1~, thì với mọi ~i = 1, 2, \ldots, K - 1~, người ~a_i~ có thể kể tiếp cho người ~a_{i+1}~.

Trong lúc tìm ra các quy tắc trên, ông Malnar đã xác định được toàn bộ các mối quan hệ bạn bè, nhưng lại quên mất những cặp nào đã đi cùng nhau tới buổi tiệc. May mắn là từ dữ liệu hiện có, thông tin này có thể khôi phục một cách duy nhất. Nói cách khác, tồn tại duy nhất một cách chia ~2N~ người thành ~N~ cặp sao cho hai người trong cùng một cặp là bạn bè.

Hãy giúp ông Malnar trả lời các câu hỏi trên.

Input

Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~, với ~1 \le N \le 5 \cdot 10^5~ và ~N \le M \le 10^6~. Đây lần lượt là số cặp cộng sự đi cùng nhau tới buổi tiệc và số quan hệ bạn bè.

~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u_i~ và ~v_i~, với ~1 \le u_i, v_i \le 2N~, biểu diễn rằng hai cộng sự đó là bạn bè.

Output

Dòng đầu tiên in ra một số nguyên ~K~: số cộng sự lớn nhất có thể nghe được câu chuyện.

Dòng thứ hai in ra một dãy ~K~ số nguyên thỏa mãn yêu cầu của đề bài.

Chấm điểm

• Subtask ~1~ (~24~ điểm): ~N \le 10~
• Subtask ~2~ (~16~ điểm): Mỗi cộng sự là bạn của không quá ~2~ người khác.
• Subtask ~3~ (~30~ điểm): ~N \le 2000~, ~M \le 5000~
• Subtask ~4~ (~40~ điểm): Không có ràng buộc bổ sung.

Sample Input ~1~

2 3
1 2
1 4
3 4

Sample Output ~1~

4
2 1 4 3

Sample Input ~2~

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

Sample Output ~2~

4
6 1 2 3

Sample Input ~3~

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

Sample Output ~3~

6
6 3 4 1 2 5

Giải thích

• Ví dụ ~1~: Các cặp đi cùng nhau là ~1~ với ~2~, và ~3~ với ~4~.
• Ví dụ ~2~: Các cặp đi cùng nhau là ~1~ với ~6~, ~2~ với ~3~, và ~4~ với ~5~. Không thể có dãy dài hơn. Chẳng hạn dãy ~[3, 2, 1, 4, 5]~ không hợp lệ dù mọi cặp liên tiếp đều là bạn bè, vì sau khi nghe từ ~2~, người ~1~ không thể kể tiếp cho ~4~ khi người đi cùng ~1~ là ~6~ vẫn chưa biết câu chuyện.
• Ví dụ ~3~: Các cặp đi cùng nhau là ~1~ với ~4~, ~2~ với ~5~, ~3~ với ~6~, và ~7~ với ~8~.