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$ 分钟再次发生，如此循环往复，无限持续。换句话说：

在第 $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$。接下来的 $K$ 行中，每行包含一对数 $(a_1,b_1) \ldots (a_K, b_K)$（$1\le a_i<b_i\le N$）。

输出格式

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

5 4
1 3
1 2
2 3
2 4

4
4
3
4
1

提示

奶牛 $1$ 到达位置集合 $\{1,2,3,4\}$。 奶牛 $2$ 到达位置集合 $\{1,2,3,4\}$。 奶牛 $3$ 到达位置集合 $\{1,2,3\}$。 奶牛 $4$ 到达位置集合 $\{1,2,3,4\}$。 奶牛 $5$ 从不移动，所以她从未离开位置 $5$。 计分： 测试点 1-5 满足 $N\le 100, K\le 200$。 测试点 6-10 满足 $N\le 2000, K\le 4000$。 测试点 11-20 无额外限制。 题目来源：Chris Zhang

标签: USACO|2021|Silver

来源

USACO|2021|Silver