시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 75 | 21 | 20 | 38.462% |
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), \ldots, (a_{K},b_{K})$. In each minute $i = 1 \ldots 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 \ldots 2K$, again in minutes $2K+1 \ldots 3K$, and so on, continuing in a cyclic fashion for a total of $M$ minutes ($1\le M\le 10^{18}$). In other words,
For each cow, please determine the number of unique positions in the line she will ever occupy.
The first line contains integers $N$, $K$, and $M$. Each of the next $K$ lines contains $(a_1,b_1) \ldots (a_K, b_K)$ ($1\le a_i<b_i\le N$).
Print $N$ lines of output, where the $i$th line contains the number of unique positions that cow $i$ reaches.
6 4 7 1 2 2 3 3 4 4 5
5 4 3 3 3 1