Description

Farmer John’s cows are showing off their latest dance moves.

At the beginning, all $N$ cows ($2 \le N \le 10^5$) stand in a line, and cow $i$ is in the $i$-th position. The dance move sequence is given as $K$ ($1 \le K \le 2 \times 10^5$) pairs of positions $(a_1,b_1),(a_2,b_2),\ldots,(a_K,b_K)$. In minute $i=1 \ldots K$ of the dance, the cows at positions $a_i$ and $b_i$ swap places. The same $K$ swaps happen again in minutes $K+1 \ldots 2K$, again in minutes $2K+1 \ldots 3K$, and so on, repeating forever. In other words,

• In minute $1$, the cows at positions $a_1$ and $b_1$ swap places.
• In minute $2$, the cows at positions $a_2$ and $b_2$ swap places.
• $\ldots$
• In minute $K$, the cows at positions $a_K$ and $b_K$ swap places.
• In minute $K+1$, the cows at positions $a_1$ and $b_1$ swap places.
• In minute $K+2$, the cows at positions $a_2$ and $b_2$ swap places.
• And so on.

For each cow, find how many distinct positions in the line she will ever occupy.

Input Format

The first line contains $N$ and $K$. The next $K$ lines each contain $(a_1,b_1)\ldots(a_K,b_K)$ ($1 \le a_i < b_i \le N$).

Output Format

Output $N$ lines. The $i$-th line contains the number of distinct positions that cow $i$ can reach.

5 4
1 3
1 2
2 3
2 4

4
4
3
4
1

Hint

• Cow $1$ can reach positions $\{1,2,3,4\}$.
• Cow $2$ can reach positions $\{1,2,3,4\}$.
• Cow $3$ can reach positions $\{1,2,3\}$.
• Cow $4$ can reach positions $\{1,2,3,4\}$.
• Cow $5$ never moves, so she never leaves position $5$.

Test Point Properties:

• Test points 1-5 satisfy $N \le 100, K \le 200$.
• Test points 6-10 satisfy $N \le 2000, K \le 4000$.
• Test points 11-20 have no additional constraints.

Problem provided by: Chris Zhang.

Translated by ChatGPT 5