学生的合流

题目描述

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

每名学生从各自的家出发后，一边与其他学生会合一边前往学校。一旦合流的学生之后不会再分开。

给定 $Q$ 个查询，请按顺序处理。查询有 $2$ 种，输入格式和查询内容如下：

• 1 a b：包含学生 $a$ 的团体与包含学生 $b$ 的团体合流（若已经合流，则什么都不发生）

• 2 x y：求在查询时已经与学生 $x$ 合流的学生（包括学生 $x$ 本身）中，属于班级 $y$ 的学生人数

输入格式

输入按以下格式从标准输入给出：

$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

2
0

在第 $3$ 个查询时，学生 $1$ 已与学生 $2,5$ 合流。学生 $1,2,5$ 中属于班级 $1$ 的学生有 $2$ 人。

在第 $5$ 个查询时，学生 $3$ 已与学生 $4$ 合流。学生 $3,4$ 中属于班级 $4$ 的学生有 $0$ 人。

5 4
2 2 2 2 2
1 1 2
1 1 3
1 2 3
2 2 2

3

对于已经属于同一团体的学生，也可能给出 1 a b 类型的查询。

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

1
0
0

数据范围

• $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$
• 输入均为整数