问题描述

有 $N$ 个学生准备去上学。学生 $i$ 属于班级 $C_i$。

离开家后，每个学生将与一群其他学生一起前往学校。一旦学生们聚在一起，他们就不会分开。

你将获得 $Q$ 个按顺序处理的查询。查询有两种格式，具体如下：

• 1 a b：包含学生 $a$ 的组和包含学生 $b$ 的组合并。（如果他们已经在同一组中，则什么也不发生。）
• 2 x y：要求在此查询时与学生 $x$（包括学生 $x$）在同一组中的班级 $y$ 的学生人数。

约束条件

• $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

在第三个查询时，学生 $1$ 加入了学生 $2$ 和 $5$。这三名学生中有两人属于班级 $1$。

在第五个查询时，学生 $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