AT_abc183_f.[ABC183F] Confluence

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

每位学生从自己家出发，途中会不断与其他学生汇合，一起前往学校。已经汇合的学生不会再分开。

现在给出 $Q$ 个查询，请按顺序处理。查询有两种类型，输入格式和内容如下：

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

样例解释 1

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

样例解释 2

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

由 ChatGPT 4.1 翻译