Confluence

题目描述

$N$ 名学生准备去上学。学生 $i$ 属于班级 $C_i$。 离开家后，每个学生会在前往学校的过程中反复与其他学生汇合。一旦学生们汇合在一起，他们就不会分开。 将按顺序给出 $Q$ 个查询。查询有两种类型，格式如下，含义为：

$1 a b$：包含学生 $a$ 的组和包含学生 $b$ 的组合并。（如果他们已经在同一组，则不发生任何事情。） $2 x y$：询问在该查询时刻，属于班级 $y$ 且已经与学生 $x$ 在同一组的学生数量（包括学生 $x$）。

输入格式

输入按如下格式从标准输入给出： $N$ $Q$ $C_1$ $\ldots$ $C_N$ $Query_1$ $\vdots$ $Query_Q$

输出格式

按格式 $2 x y$ 输出这些查询的答案，每个占一行，按顺序输出。

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

2
0

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

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

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$。 输入中的所有数值均为整数。在第 $3$ 个查询时，学生 $1$ 已经与学生 $2$ 和 $5$ 汇合。在这三名学生中，有两名属于班级 $1$。 在第 $5$ 个查询时，学生 $3$ 已经与学生 $4$ 汇合。在这两名学生中，没有人属于班级 $4$。
可能会有针对已经属于同一组的学生的格式为 $1 a b$ 的查询。

标签: AtCoder|abc183F

来源

AtCoder|abc183F