Farmer John's cows are showing off their new dance mooves! At first, all $N$ cows $(2\le N\le 10^5)$ stand in a line with cow $i$ in the $i$-th position in line. The sequence of dance mooves is given by $K$ $(1\le K\le 2\cdot 10^5)$ pairs of positions $(a_1,b_1),(a_2,b_2),\cdots,(a_K,b_K)$. In each minute $i=1\cdots K$ of the dance, the cows in positions $a_i$ and $b_i$ in line swap. The same $K$ swaps happen again in minutes $K+1\cdots 2K$, again in minutes $2K+1\cdots 3K$, and so on, continuing in a cyclic fashion for a total of $M$ minutes $(1\le M\le 10^{18})$. In other words, - In minute $1$, the cows at positions $a_1$ and $b_1$ swap. - In minute $2$, the cows at positions $a_2$ and $b_2$ swap. - ... - In minute $K$, the cows in positions $a_K$ and $b_K$ swap. - In minute $K+1$, the cows in positions $a_1$ and $b_1$ swap. - In minute $K+2$, the cows in positions $a_2$ and $b_2$ swap. - and so on ... For each cow, please determine the number of unique positions in the line she will ever occupy. Farmer John 的奶牛们正在炫耀她们的最新舞步！ 最初，所有的 $N$ 头奶牛（$2≤N≤10^5$）站成一行，奶牛 $i$ 排在其中第 $i$ 位。舞步序列给定为 $K$ （$1≤K≤2\times10^5$）个位置对 $(a_1,b_1),(a_2,b_2),…,(a_K,b_K)$。在舞蹈的第 $i=1…K$ 分钟，位置 $a_i$ 与 $b_i$ 上的奶牛交换位置。同样的 $K$ 次交换在第 $K+1…2K$ 分钟发生，在第 $2K+1…3K$ 分钟再次发生，以此类推，周期性地持续共 $M$ 分钟（$1≤M≤10^{18}$）。换言之， - 在第 $1$ 分钟，位置 $a_1$ 与 $b_1$ 上的奶牛交换位置。 - 在第 $2$ 分钟，位置 $a_2$ 与 $b_2$ 上的奶牛交换位置。 - …… - 在第 $K$ 分钟，位置 $a_K$ 与 $b_K$ 上的奶牛交换位置。 - 在第 $K+1$ 分钟，位置 $a_1$ 与 $b_1$ 上的奶牛交换位置。 - 在第 $K+2$ 分钟，位置 $a_2$ 与 $b_2$ 上的奶牛交换位置。 - 以此类推…… 对于每头奶牛，求她在队伍中会占据的不同的位置数量。

The first line contains integers $N$, $K$, and $M$. Each of the next $K$ lines contains $(a_1,b_1)\cdots (a_K,b_K)$ $(1\le a_i\lt b_i\le N)$.

Print $N$ lines of output, where the $i$-th line contains the number of unique positions that cow $i$ reaches.

After $7$ minutes, the cows in increasing order of position are $[3,4,5,2,1,6]$. - Cow $1$ reaches positions $\{1,2,3,4,5\}$. - Cow $2$ reaches positions $\{1,2,3,4\}$. - Cow $3$ reaches positions $\{1,2,3\}$. - Cow $4$ reaches positions $\{2,3,4\}$. - Cow $5$ reaches positions $\{3,4,5\}$. - Cow $6$ never moves, so she never leaves position $6$.

USACO 2021 January Contest, Gold