Sau khi ba tỉnh Hà Nam, Nam Định, Ninh Bình được sáp nhập thành tỉnh Ninh Bình, giám đốc một siêu thị sữa muốn tri ân khách hàng trong tỉnh bằng cách tặng cho mỗi khách hàng một hộp sữa mà họ yêu thích. Nhân viên siêu thị được giao nhiệm vụ khảo sát ý kiến của ~n~ khách hàng (được đánh số thứ tự ~1, 2, \dots, n~) về tên của hai hãng sữa họ yêu thích và thứ tự ưu tiên (nhất, nhì) khi chọn mua sữa. Siêu thị đang bán ~m~ hãng sữa khác nhau (được đánh số thứ tự ~1, 2, \dots, m~). Để tiết kiệm chi phí và quảng bá các hãng sữa đến khách hàng, giám đốc siêu thị quyết định mỗi hãng sữa chỉ tặng một hộp sữa duy nhất. Điều này có thể dẫn tới việc một số khách hàng không thể nhận được hộp sữa mà mình yêu thích. Với những khách hàng như vậy, siêu thị sẽ tặng một phiếu giảm giá khi mua hàng lần sau. Để thực hiện được công việc, nhân viên siêu thị sẽ gọi lần lượt từng khách hàng trong ~n~ khách hàng, sau đó tặng quà theo các bước:

• Bước 1. Nếu có hộp sữa yêu thích nhất, khách hàng được tặng hộp sữa này và ra về.

• Bước 2. Nếu không có hộp sữa yêu thích nhất và có hộp sữa yêu thích nhì, khách hàng được tặng một hộp sữa này và ra về.

• Bước 3. Nếu không có hộp sữa yêu thích nhất và nhì, khách hàng không thể nhận được hộp sữa mình yêu thích. Khi đó, khách hàng nhận được một phiếu giảm giá và ra về.

Yêu cầu: Tìm ra một cách gọi lần lượt các khách hàng tối ưu nhất (hay tìm ra một hoán vị của tập hợp ~\{1, 2, 3, \dots, n\}~) sao cho số lượng khách hàng không thể nhận được hộp sữa mà mình yêu thích là tối thiểu.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, m~ ~(1 \le n \le 10^5; 2 \le m \le 10^5)~;

• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo, chứa hai số nguyên ~f_i, s_i~, lần lượt là số hiệu hãng sữa khách hàng thứ ~i~ yêu thích nhất và nhì ~(1 \le f_i, s_i \le m; f_i \ne s_i)~;

• Các số trong mỗi dòng cách nhau bằng dấu cách.

Output

• Dòng đầu tiên chứa một số nguyên là số lượng tối thiểu các khách hàng không thể nhận được sữa.

• ~n~ dòng tiếp theo chứa một hoán vị của tập ~\{1, 2, \dots, n\}~, thể hiện trình tự các khách hàng được lựa chọn tặng quà, mỗi phần tử của hoán vị nằm trên một dòng. Nếu có nhiều hoán vị thỏa mãn thì có thể ghi ra một hoán vị bất kỳ.

Scoring

Sample Input 1

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

Sample Output 1

1
1
3
2
8
4
6
5
7

Notes

• Trong ví dụ trên có ~8~ khách hàng và ~10~ hãng sữa, mỗi hãng sữa được tặng một hộp sữa duy nhất. Lưu ý rằng chúng ta có thể thực hiện xếp ~3~ khách hàng đầu tiên độc lập với ~5~ khách hàng cuối cùng vì không có chung hãng sữa yêu thích.

• Nếu ~3~ khách hàng đầu tiên được gọi theo thứ tự ~1 \rightarrow 2 \rightarrow 3~ thì khách hàng ~1~ nhận được hộp sữa số ~2~, khách hàng ~2~ nhận được hộp sữa số ~3~ và khách hàng ~3~ không thể nhận được hộp sữa nào cả.

• Nếu ~3~ khách hàng đầu tiên được gọi theo thứ tự ~1 \rightarrow 3 \rightarrow 2~ thì khách hàng ~1~ nhận được hộp sữa số ~2~, khách hàng ~3~ nhận được hộp sữa số ~3~, khách hàng ~2~ sẽ nhận được hộp sữa số ~4~. Như vậy cả ~3~ khách hàng đều nhận được sữa.

• Có thể có các hoán vị khác của ~3~ khách hàng đầu tiên sao cho các khách hàng này đều nhận được sữa yêu thích. Ví dụ như ~3 \rightarrow 1 \rightarrow 2~.

• Tương tự với ~5~ khách hàng cuối cùng có thể được gọi theo thứ tự ~8 \rightarrow 4 \rightarrow 6 \rightarrow 5 \rightarrow 7~. Khách hàng ~8~ sẽ nhận được hộp sữa số ~5~, khách hàng ~4~ sẽ nhận được hộp sữa số ~6~, khách hàng ~6~ sẽ nhận được hộp sữa số ~7~, khách hàng ~5~ sẽ nhận được hộp sữa số ~8~, khách hàng ~7~ sẽ không thể nhận được hộp sữa yêu thích.