Dance Mooves

题目描述

Farmer John 的奶牛正在炫耀她们新学的舞步！ 一开始，所有 $N$ 头奶牛（$2\le N\le 10^5$）站成一排，奶牛 $i$ 位于队列中的第 $i$ 个位置。舞步序列由 $K$（$1\le K\le 2\cdot 10^5$）对位置 $(a_1,b_1), (a_2,b_2), \ldots, (a_{K},b_{K})$ 给出。在舞蹈的每一分钟 $i = 1 \ldots K$，队列中位于位置 $a_i$ 和 $b_i$ 的两头奶牛交换位置。相同的这 $K$ 次交换会在第 $K+1 \ldots 2K$ 分钟再次发生，在第 $2K+1 \ldots 3K$ 分钟再次发生，如此循环往复，总共持续 $M$ 分钟（$1\le M\le 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}$ 上的奶牛交换。 以此类推…… 对于每一头奶牛，请确定她在整个过程中曾经占据过的不同位置的数量。 注意：本题每个测试用例的时间限制是默认值的两倍。

输入格式

第一行包含整数 $N$、$K$ 和 $M$。接下来的 $K$ 行每行包含一对数 $(a_1,b_1) \ldots (a_K, b_K)$（$1\le a_i<b_i\le N$）。

输出格式

输出共 $N$ 行，其中第 $i$ 行输出奶牛 $i$ 到达过的不同位置的数量。

6 4 7
1 2
2 3
3 4
4 5

5
4
3
3
3
1

提示

经过 $7$ 分钟后，按位置从小到大排列的奶牛为 $[3,4,5,2,1,6]$。 奶牛 $1$ 到达的位置为 $\{1,2,3,4,5\}$。 奶牛 $2$ 到达的位置为 $\{1,2,3,4\}$。 奶牛 $3$ 到达的位置为 $\{1,2,3\}$。 奶牛 $4$ 到达的位置为 $\{2,3,4\}$。 奶牛 $5$ 到达的位置为 $\{3,4,5\}$。 奶牛 $6$ 从不移动，因此她从未离开位置 $6$。 计分： 测试点 1-5 满足 $N\le 100, K\le 200$。 测试点 6-10 满足 $M=10^{18}$。 测试点 11-20 没有额外限制。 题目来源：Chris Zhang

标签: USACO|2021|Gold

来源

USACO|2021|Gold