#PU1091. USACO 2021 January Contest, Gold — Problem 3. Dance Mooves

    ID: 1481 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan21来源:usaco.orgscoring:equal_test_cases模拟

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 NN cows (2≤N≤1052\le N\le 10^5) stand in a line with cow ii in the iith position in line. The sequence of dance mooves is given by KK (1≤K≤2⋅1051\le K\le 2\cdot 10^5) pairs of positions (a1,b1),(a2,b2),…,(aK,bK)(a_1,b_1), (a_2,b_2), \ldots, (a_{K},b_{K}). In each minute i=1…Ki = 1 \ldots K of the dance, the cows in positions aia_i and bib_i in line swap. The same KK swaps happen again in minutes K+1…2KK+1 \ldots 2K, again in minutes 2K+1…3K2K+1 \ldots 3K, and so on, continuing in a cyclic fashion for a total of MM minutes (1≤M≤10181\le M\le 10^{18}). In other words, In minute 11, the cows at positions a1a_1 and b1b_1 swap. In minute 22, the cows at positions a2a_2 and b2b_2 swap. ... In minute KK, the cows in positions aKa_{K} and bKb_{K} swap. In minute K+1K+1, the cows in positions a1a_{1} and b1b_{1} swap. In minute K+2K+2, the cows in positions a2a_{2} and b2b_{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 (a1,b1)…(aK,bK)(a_1,b_1) \ldots (a_K, b_K) (1≤ai<bi≤N1\le a_i<b_i\le N).

输出格式

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

数据范围

Test cases 1-5 satisfy N≤100,K≤200N\le 100, K\le 200. Test cases 6-10 satisfy M=1018M=10^{18}. 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$.