Description

Farmer John has $N$ cows, and each cow has a favorite color. The cows are numbered $1\ldots N$, and each color can also be represented by an integer in $1\ldots N$.

There are $M$ pairs of cows $(a,b)$ where cow $b$ admires cow $a$. 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 whose favorite color is $c$, then cows $x$ and $y$ have the same favorite color.

Given this information, find an assignment of favorite colors to cows such that the number of distinct favorite colors among all cows is maximized. Since there may be multiple assignments that achieve this, output the lexicographically smallest one (meaning you should minimize, in order, the colors assigned to cows $1 \ldots N$).

Input Format

The first line contains $N$ and $M$.
The next $M$ lines each contain two space-separated integers $a$ and $b$ ($1\le a,b\le N$), indicating that cow $b$ admires cow $a$. The same pair of cows may appear multiple times in the input.

Output Format

For each $i$ in $1\ldots N$, output the color assigned to cow $i$ on its own line.

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

1
2
3
1
1
2
3
2
3

Hint

Sample Explanation:

In the figure below, cows with a thick-bordered circle are those whose favorite color is $1$.

Constraints: for $100\%$ of the testdata, $1\le N,M\le 2\times 10^5$.

There are $10$ test points. Point $1$ is the sample, and the remaining points have the following properties:

Test points $2\sim 3$ satisfy $N,M\le 10^3$.
Test points $4\sim 10$ have no additional constraints.

Problem authors: William Lin, Benjamin Qi.

Translated by ChatGPT 5