分数: 600 点
问题陈述
N 学生们即将上学。学生 i 属于类 C_i.
离开家后,每个学生都会前往学校,同时反复与其他学生会合。学生一旦结合在一起,就不会分开。
你将得到 Q 应按顺序处理的查询。有两种查询,其格式如下,含义如下:
1 a b:包含 Student 的组 a 和包含 Student 的组 b 合并。 (如果他们已经在同一组中,则不会发生任何事情。)2 x y:要求您查找属于班级的学生人数 y 已与学生在同一组中的人 x (包括学生 x)在此查询时。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq C_i,a,b,x,y \leq N
- 在查询中的格式
1 a b, a \neq b. - 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q C_1 \ldots C_N Query_1 \vdots Query_Q
输出
以以下格式打印查询的答案 2 x y,每个都在自己的行中,按顺序。
示例输入 1
5 5 1 2 3 2 1 1 1 2 1 2 5 2 1 1 1 3 4 2 3 4
示例输出 1
2 0
当时 3-rd 查询,学生 1 已加入学生 2 和 5。这三名学生中,有两名属于班级 1.
当时 5第一个查询,学生 3 已加入学生 4。这两个学生,都不属于班级 4.
示例输入 2
5 4 2 2 2 2 2 1 1 2 1 1 3 1 2 3 2 2 2
示例输出 2
3
格式可能有疑问 1 a b 适用于已经属于同一组的学生。
示例输入 3
12 9 1 2 3 1 2 3 1 2 3 1 2 3 1 1 2 1 3 4 1 5 6 1 7 8 2 2 1 1 9 10 2 5 6 1 4 8 2 6 1
示例输出 3
1 0 0