Dance Mooves

문제

Farmer John’s cows are showing off their new dance mooves!

At first, all $NN$ cows ($2\le N\le {10}^{5}2\backslash le\; N\backslash le\; 10^5$) stand in a line with cow $ii$ in the $ii$th position in line. The sequence of dance mooves is given by $KK$ ($1\le K\le 2\cdot {10}^{5}1\backslash le\; K\backslash le\; 2\backslash cdot\; 10^5$) pairs of positions $(a_1,b_1),(a_2,b_2),\dots ,(a_K,b_K)(a\_1,b\_1),\; (a\_2,b\_2),\; \backslash ldots,\; (a\_\{K\},b\_\{K\})$. In each minute $i=1\dots Ki\; =\; 1\; \backslash ldots\; K$ of the dance, the cows in positions $a_{i}a\_i$ and $b_{i}b\_i$ in line swap. The same $KK$ swaps happen again in minutes $K+1\dots 2KK+1\; \backslash ldots\; 2K$, again in minutes $2K+1\dots 3K2K+1\; \backslash ldots\; 3K$, and so on, continuing in a cyclic fashion for a total of $MM$ minutes ($1\le M\le {10}^{18}1\backslash le\; M\backslash le\; 10^\{18\}$). In other words,

• In minute $11$, the cows at positions $a_{1}a\_1$ and $b_{1}b\_1$ swap.
• In minute $22$, the cows at positions $a_{2}a\_2$ and $b_{2}b\_2$ swap.
• ...
• In minute $KK$, the cows in positions $a_{K}a\_\{K\}$ and $b_{K}b\_\{K\}$ swap.
• In minute $K+1K+1$, the cows in positions $a_{1}a\_\{1\}$ and $b_{1}b\_\{1\}$ swap.
• In minute $K+2K+2$, the cows in positions $a_{2}a\_\{2\}$ and $b_{2}b\_\{2\}$ swap.
• and so on ...

For each cow, please determine the number of unique positions in the line she will ever occupy.

입력

The first line contains integers $NN$, $KK$, and $MM$. Each of the next $KK$ lines contains $(a_1,b_1)\dots (a_K,b_K)(a\_1,b\_1)\; \backslash ldots\; (a\_K,\; b\_K)$ ().

출력

Print $NN$ lines of output, where the $ii$th line contains the number of unique positions that cow $ii$ reaches.