Mỗi con bò trong N con bò của Nông dân John (1 ≤ N≤ 2*10^5) 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*10^5). 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).

INPUT

• 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.

OUTPUT:

Với mỗi con bò thứ i trong các con bò từ 1 …N, ghi màu yêu thích của con bò nó tương ứng.

Sample Input

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

Sample Output

1 
2 
3 
1 
1 
2 
3 
2 
3