Mô tả và yêu cầu

Mỗi con bò trong N con bò của Nông dân John (1 ≤ N≤ 2*105) có một màu yêu
thích. Những con bò được dán nhãn 1 … N và mỗi màu có thể được biểu thị bằng
một số nguyên trong phạm vi 1…N.

Có M cặp bò (a,b) mô tả cho con bò b ngưỡng mộ con bò a (1 ≤ M≤ 2*105). Có thể
là a = b, trong trường hợp đó con bò tự ngưỡng mộ chính mình. Đối với một màu c
bất kì, nếu có 2 con bò x và y cùng ngưỡng mộ con bò a có màu sắc yêu thích c, thì
con bò x và y cũng yêu thích màu c.

Với thông tin này, hãy xác định việc gán màu sắc ưa thích của các con bò sao cho
số lượng màu sắc ưa thích riêng biệt giữa tất cả các con bò là tối đa. Vì có nhiều
cách gán đáp ứng yêu cầu này, hãy xuất ra đáp án nhỏ nhất về mặt từ vựng (nghĩa là
bạn nên gán màu cho các con bò theo thứ tự từ 1 .. N).

Dữ liệu vào

 Dòng đầu tiên chứa N và M.
 Tiếp theo M dòng, mỗi dòng chứa hai số nguyên được phân tách bằng dấu
cách a và b (1 ≤ a , b ≤ N), biểu thị con bò b ngưỡng mộ con bò a. Cùng một
cặp có thể xuất hiện nhiều lần trong đầu vào.

Dữ liệu ra

Với mỗi con bò thứ i trong các con bò từ 1 …N, ghi ra thiết bị xuất chuẩn màu yêu
thích của con bò thứ i tương ứng.

Ví dụ

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

Trong hình dưới đây, các vòng tròn có đường viền in đậm đại diện cho những con
bò có màu yêu thích 1.