P7298 [USACO21JAN] Dance Mooves G

Farmer John's cows are showing off their newest dance moves. At the beginning, all $N$ cows ($2 \le N \le 10^5$) stand in a line, and cow $i$ is in position $i$. A 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)$. During minute $i = 1 \ldots K$ of the dance, the cows in positions $a_i$ and $b_i$ swap positions. The same $K$ swaps happen again during minutes $K+1 \ldots 2K$, again during minutes $2K+1 \ldots 3K$, and so on, repeating periodically for a total of $M$ minutes ($1 \le M \le 10^{18}$). In other words: - In minute $1$, the cows in positions $a_1$ and $b_1$ swap positions. - In minute $2$, the cows in positions $a_2$ and $b_2$ swap positions. - $\ldots$ - In minute $K$, the cows in positions $a_K$ and $b_K$ swap positions. - In minute $K+1$, the cows in positions $a_1$ and $b_1$ swap positions. - In minute $K+2$, the cows in positions $a_2$ and $b_2$ swap positions. - And so on. For each cow, find how many distinct positions she will occupy in the line. Note: For this problem, the time limit for each test case is twice the default time limit.

The first line contains $N$, $K$, and $M$. The next $K$ lines each contain $(a_i, b_i)$ ($1 \le a_i < b_i \le N$).

Output $N$ lines. Line $i$ should contain the number of distinct positions that cow $i$ can reach.

After $7$ minutes, the cows in each position are $[3, 4, 5, 2, 1, 6]$. - Cow $1$ can reach positions $\{1, 2, 3, 4, 5\}$. - Cow $2$ can reach positions $\{1, 2, 3, 4\}$. - Cow $3$ can reach positions $\{1, 2, 3\}$. - Cow $4$ can reach positions $\{2, 3, 4\}$. - Cow $5$ can reach positions $\{3, 4, 5\}$. - Cow $6$ never moved, so she has never left position $6$. #### Testdata Properties: - Testdata $1$-$5$ satisfy $N \le 100, K \le 200$. - Testdata $6$-$10$ satisfy $M = 10^{18}$. - Testdata $11$-$20$ have no additional constraints. Problem credits: Chris Zhang. Translated by ChatGPT 5