Favorite Colors

문제

Each of Farmer John's $NN$ cows ($1\le N\le 2\cdot {10}^{5}1\backslash le\; N\backslash le\; 2\backslash cdot\; 10^5$) has a favorite color. The cows are conveniently labeled $1\dots N1\backslash ldots\; N$ (as always), and each color can be represented by an integer in the range $1\dots N1\backslash ldots\; N$.

There exist $MM$ pairs of cows $(a,b)(a,b)$ such that cow $bb$ admires cow $aa$ ($1\le M\le 2\cdot {10}^{5}1\backslash le\; M\backslash le\; 2\backslash cdot\; 10^5$). It is possible that $a=ba=b$, in which case a cow admires herself. For any color $cc$, if cows $xx$ and $yy$ both admire a cow with favorite color $cc$, then $xx$ and $yy$ 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\dots N1\backslash ldots\; N$ in that order).

입력

The first line contains $NN$ and $MM$.

The next $MM$ lines each contain two space-separated integers $aa$ and $bb$ ($1\le a,b\le N1\backslash le\; a,b\backslash le\; N$), denoting that cow $bb$ admires cow $aa$. The same pair may appear more than once in the input.

출력

For each $ii$ in $1\dots N1\backslash ldots\; N$, output the color of cow $ii$ in the desired assignment on a new line.

힌트

In the image below, the circles with bolded borders represent the cows with favorite color 1.

[이미지 1]