问题 F: Favorite Colors

Farmer John 的 N 头奶牛每头都有一种最喜欢的颜色。奶牛们的编号为 1…N，每种颜色也可以用 1…N 中的一个整数表示。存在 M 对奶牛 (a,b)，奶牛 b 仰慕奶牛 a。有可能 a=b，此时一头奶牛仰慕她自己。对于任意颜色 c，如果奶牛 x 和 y 都仰慕一头喜欢颜色 c 的奶牛，那么 x 和 y 喜欢的颜色相同。给定这些信息，求一种奶牛喜欢颜色的分配方案，使得每头奶牛最喜欢的颜色中不同颜色的数量最大。由于存在多种符合这一性质的分配方案，输出字典序最小的方案（这意味着你应当依次最小化分配给奶牛 1…N 的颜色）。

Each of Farmer John's N cows (1≤N≤2⋅105) has a favorite color. The cows are conveniently labeled 1…N (as always), and each color can be represented by an integer in the range 1…N. There exist M pairs of cows (a,b) such that cow b admires cow a (1≤M≤2⋅105). It is possible that a=b, in which case a cow admires herself. For any color c, if cows x and y both admire a cow with favorite color c, then x and y share the same favorite color. Given this information, determine an assignment of cows to favorite colors such that the number of distinct favorite colors among all cows is maximized. As there are multiple assignments that satisfy this property, output the lexicographically smallest one (meaning that you should take the assignment that minimizes the colors assigned to cows 1…N in that order).


INPUT FORMAT (file fcolor.in): The first line contains N and M. The next M lines each contain two space-separated integers a and b (1≤a,b≤N), denoting that cow b admires cow a. The same pair may appear more than once in the input. 


OUTPUT FORMAT (file fcolor.out): For each i in 1…N, output the color of cow i in the desired assignment on a new line. 


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 In the image below, the circles with bolded borders represent the cows with favorite color 1. 


SCORING: Test cases 2-3 satisfy N,M≤103. Test cases 4-10 satisfy no additional constraints. 


Problem credits: William Lin and Benjamin Qi