Không gì khiến những chú bò của Nông dân John thích hơn ngũ cốc vào bữa sáng! Thực tế, đàn bò ăn khỏe đến mức mỗi con sẽ ăn hết cả một hộp ngũ cốc trong một bữa.

Trang trại vừa nhận một lô hàng gồm \(M\) loại ngũ cốc khác nhau (\(2\le M\le 10^5\)). Không may, mỗi loại chỉ có một hộp! Mỗi chú bò trong số \(N\) chú bò (\(1\le N\le 10^5\)) có một loại ngũ cốc yêu thích nhất và một loại yêu thích thứ hai. Khi được cho một số loại ngũ cốc để lựa chọn, một chú bò thực hiện quy trình sau:

1. Nếu hộp ngũ cốc yêu thích nhất của cô bò vẫn còn, cô lấy nó rồi rời đi.
2. Nếu không, nếu hộp ngũ cốc yêu thích thứ hai của cô vẫn còn, cô lấy nó rồi rời đi.
3. Nếu vẫn không được, cô rống lên thất vọng và rời đi mà không lấy ngũ cốc.

Hãy tìm số bò bị đói nhỏ nhất nếu bạn sắp xếp chúng theo thứ tự tối ưu. Đồng thời, hãy tìm một hoán vị bất kỳ của \(N\) chú bò đạt được giá trị nhỏ nhất này.

Dữ liệu vào

Dòng đầu chứa hai số nguyên cách nhau bởi dấu cách \(N\) và \(M\).

Với mỗi \(1\le i\le N\), dòng thứ \(i\) chứa hai số nguyên cách nhau bởi dấu cách \(f_i\) và \(s_i\) (\(1\le f_i,s_i\le M\) và \(f_i\ne s_i\)), lần lượt biểu thị loại ngũ cốc yêu thích nhất và yêu thích thứ hai của chú bò thứ \(i\).

Dữ liệu ra

In số bò bị đói nhỏ nhất, sau đó là một hoán vị bất kỳ của \(1\ldots N\) đạt được giá trị nhỏ nhất này. Nếu có nhiều hoán vị, có thể in bất kỳ hoán vị nào.

Phân nhóm

• Trong \(4\) trên tổng số \(14\) test, \(N,M\le 100\).
• Trong \(10\) trên tổng số \(14\) test, không có ràng buộc bổ sung.

Ví dụ

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

1
1
3
2
8
4
6
5
7

Nguồn

USACO 2022 January Contest, Silver — Cereal 2: https://usaco.org/index.php?page=viewproblem2&cpid=1184

Tác giả: Dhruv Rohatgi.