P7299 [USACO21JAN] Dance Mooves S

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.

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 $N$ lines. The $i$-th line contains the number of distinct positions that cow $i$ can reach.

- 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