#PU1091. USACO 2021 January Contest, Gold — Problem 3. Dance Mooves
USACO 2021 January Contest, Gold — Problem 3. Dance Mooves
USACO 2021 January Contest, Gold — Problem 3. Dance Mooves
题目描述
Farmer John’s cows are showing off their new dance mooves! At first, all cows () stand in a line with cow in the th position in line. The sequence of dance mooves is given by () pairs of positions . In each minute of the dance, the cows in positions and in line swap. The same swaps happen again in minutes , again in minutes , and so on, continuing in a cyclic fashion for a total of minutes (). In other words, In minute , the cows at positions and swap. In minute , the cows at positions and swap. ... In minute , the cows in positions and swap. In minute , the cows in positions and swap. In minute , the cows in positions and 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 , , and . Each of the next lines contains ().
输出格式
Print lines of output, where the th line contains the number of unique positions that cow reaches.
数据范围
Test cases 1-5 satisfy . Test cases 6-10 satisfy . Test cases 11-20 satisfy no additional constraints. Problem credits: Chris Zhang
样例
样例 1
6 4 7
1 2
2 3
3 4
4 5
5
4
3
3
3
1
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$.