Mỗi con trong số \(N\) con bò của Nông dân John (\(1 \leq N \leq 2\cdot 10^5\)) có một màu yêu thích. Những con bò được đánh số thuận tiện từ \(1 \ldots N\) (như mọi khi), và mỗi màu có thể được biểu diễn bằng một số nguyên trong phạm vi \(1 \ldots N\).

Tồn tại \(M\) cặp bò \((a,b)\) sao cho bò \(b\) ngưỡng mộ bò \(a\) (\(1 \leq M \leq 2\cdot 10^5\)). Có thể xảy ra \(a=b\), trong trường hợp đó một con bò ngưỡng mộ chính nó. Với bất kỳ màu \(c\) nào, nếu mỗi con trong hai con bò \(x\) và \(y\) đều ngưỡng mộ một con bò có màu yêu thích là \(c\), thì \(x\) và \(y\) có cùng màu yêu thích.

Dựa trên thông tin này, hãy xác định một cách gán màu yêu thích cho những con bò sao cho số màu yêu thích phân biệt trong toàn bộ đàn bò là lớn nhất. Vì có nhiều cách gán thỏa mãn tính chất này, hãy in ra cách có thứ tự từ điển nhỏ nhất (nghĩa là chọn cách gán lần lượt tối thiểu hóa màu được gán cho các con bò \(1 \ldots N\) theo thứ tự đó).

Dữ liệu vào

Tệp fcolor.in:

Dòng đầu tiên chứa \(N\) và \(M\).

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) cách nhau bởi dấu cách (\(1 \leq a,b \leq N\)), biểu thị rằng bò \(b\) ngưỡng mộ bò \(a\). Cùng một cặp có thể xuất hiện nhiều lần trong dữ liệu vào.

Dữ liệu ra

Tệp fcolor.out:

Với mỗi \(i\) từ \(1 \ldots N\), in màu của bò \(i\) trong cách gán cần tìm trên một dòng mới.

Phân nhóm

• Các test 2–3 thỏa mãn \(N,M \leq 10^3\).
• Các test 4–10 không có ràng buộc bổ sung.

Ví dụ

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

1
2
3
1
1
2
3
2
3

Nguồn

USACO 2020 US Open Contest, Gold — Favorite Colors

Tác giả bài: William Lin và Benjamin Qi.