Maximizing Distinct Favorite Colors

Farmer John has N cows, numbered from $1$ to $N$. Each cow has a favorite color represented by an integer from $1$ to $N$. There are M admiration pairs $(a,b)$ meaning that cow b admires cow a (note that it is possible that $a=b$, meaning a cow may even admire herself). The cows must be assigned a favorite color subject to the following constraint:

For any color $c$, if cows $x$ and $y$ both admire a cow whose favorite color is $c$, then they must share the same favorite color, i.e., $$\text{if}\; \exists\; v\; \text{with}\; f(v)=c \;\text{and}\; (v,x),(v,y) \text{ are admiration pairs, then } f(x)=f(y).$$

Your task is to determine an assignment of favorite colors for all cows so that the total number of distinct colors used is maximized. If there are multiple assignments that achieve the maximum number of distinct colors, output the lexicographically smallest assignment (i.e. minimize $f(1)$, then $f(2)$, and so on).

inputFormat

The first line contains two integers N and M ($1\leq N\leq 10^5$, $0\leq M\leq 10^5$), representing the number of cows and the number of admiration pairs.

Each of the next M lines contains two integers a and b ($1 \leq a,b \leq N$), indicating that cow b admires cow a.

outputFormat

Output a single line containing N integers. The i-th integer denotes the assigned favorite color of cow i. The assignment must maximize the number of distinct colors used, and among all optimal assignments, be lexicographically smallest.

sample

3 2
1 2
1 3

1 2 2