P6901: 舞驼鹿

---

【题目描述】

【题目描述】
Farmer John 的奶牛们正在炫耀她们的最新舞步！
最初，所有的 N 头奶牛（2≤N≤10^5）站成一行，奶牛 i 排在其中第 i 位。舞步序列给定为 K 个位置对 (a1,b1),(a2,b2),…,(aK,bK)。在舞蹈的第i=1…K 分钟，位置 ai 与 bi 上的奶牛交换位置。同样的 K 次交换在第 K+1…2K 分钟发生，在第 2K+1…3K 分钟再次发生，以此类推，无限循环。换言之，
l 在第 1 分钟，位置 a1 与 b1 上的奶牛交换位置。
l 在第 2 分钟，位置 a2 与 b2 上的奶牛交换位置。
l ……
l 在第 K 分钟，位置 aK 与 bK 上的奶牛交换位置。
l 在第 K+1 分钟，位置 a1 与 b1 上的奶牛交换位置。
l 在第 K+2 分钟，位置 a2 与 b2 上的奶牛交换位置。
l 以此类推……
对于每头奶牛，求她在队伍中会占据的不同的位置数量。
【输入格式】（从终端/标准输入读入）：
输入的第一行包含 N 和 K。以下 K 行分别包含 (a1,b1)…(aK,bK)（1≤ai<bi≤N）。
【输出格式】（输出至终端/标准输出）：
输出 N 行，第 i 行包含奶牛 i 可以到达的不同的位置数量。
【输入样例】：
5 4
1 3
1 2
2 3
2 4
【输出样例】：
4
4
3
4
1
【样例说明】
l 奶牛 1 可以到达位置 {1,2,3,4}。
l 奶牛 2 可以到达位置 {1,2,3,4}。
l 奶牛 3 可以到达位置 {1,2,3}。
l 奶牛 4 可以到达位置 {1,2,3,4}。
l 奶牛 5 从未移动，所以她没有离开过位置 5。
【测试点性质】：
测试点 1-5 满足N≤100,K≤200。
测试点 6-10 满足 N≤2000,K≤4000。
测试点 11-20 没有额外限制。
 

题目类型~

USACO-2021-银-1月 

咻咻~

提交答案 状态 返回