花车巡游
题目描述
嘉年华的花车巡游正在展示精心编排的队列变换！
最初，所有 N辆花车排成一行，花车 i 位于第 i 位。变换程序由 K 个位置对 (a1,b1),(a2,b2),…,(aK,bK) 描述。表演过程中：
· 第 1 分钟：位置 a1 与 b1 的花车交换位置
· 第 2 分钟：位置 a2 与 b2 的花车交换位置
· ……
· 第 K 分钟：位置 aK 与 bK 的花车交换位置
· 第 K+1 分钟：重新从 (a1,b1) 开始交换（即位置 a1 与 b1 交换）
· 第 K+2 分钟：位置 a2 与 b2 交换
· 如此无限循环……
请计算每辆花车在整个表演过程中能到达的不同位置数量。
输入格式
第一行输入 N,K。
接下来 K 行每行包含 ai,bi（1≤ai<bi≤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≤K≤2×105
2≤N≤105
限制
时间限制：1000ms
内存限制：256MiB
相似题推荐
专属教室
题目描述
在一所学校中，有 N 个班级，每个班级都有一间专属的教室。第 i 个班级当前使用的教室编号为 Si，但学校计划将其调整到新的教室 Ti。
已知所有班级当前使用的教室编号互不相同，所有班级希望更换到的教室编号也互不相同。每个班级只能更换一次教室，且一次只能安排一个班级进行更换。在更换时，目标教室必须是空闲的。
学校希望找到一个合理的更换顺序，使得所有班级都能顺利迁入目标教室。请判断是否可能。
输入格式
第一行一个整数 N。
接下来 N 行，每行两个字符串 Si 和 Ti，表示第 i 个班级当前所在的教室编号和希望迁入的教室编号。
输出格式
如果存在一种顺序使得所有班级都能完成更换，输出 Yes，否则输出 No。
输入样例#1
2 b m m d
输出样例#1
Yes
输入样例#2
3 a b b c c a
输出样例#2
No
说明提示
1≤N≤105
Si,Ti 为由小写英文字母组成的字符串，长度在 1 到 8 之间。
Si≠Ti
所有 Si 互不相同。
所有 Ti 互不相同。
限制
时间限制：1000ms
内存限制：256MiB
