Problem Description

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.

Input Format

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 Format

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

6 4 7
1 2
2 3
3 4
4 5

5
4
3
3
3
1

Hint

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