← 返回题目列表

AtCoder · abc183_f

F. 汇合

中文机器翻译题面 查看原题

分数: 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