并查集

题目描述

给定从 $1$ 到 $n$ 共 $n$ 个整数，一开始每个整数 $i$ 属于一个独立的集合 $\{i\}$。现在共有 $m$ 条指令将被执行，这些指令分为如下三类：

1. $1 \ x \ y$，将 $x$ 所属的集合 $S_x$ 与 $S_y$合并。
2. $2 \ x$，查询 $x$ 所属集合的代表元素 $p$，规定一个集合的代表元素为 $p = \min(S), p \in s$。
3. $3 \ x$，查询 $x$ 所属集合的大小。

输入格式

输入第一行包含两个整数 $n,m$，表示初始集合个数和指令总数。 随后每行包含一条如上格式的指令。

op x (y)

数据范围

$1 \le n,m \le 10^5$ $op \in \{1,2,3\}$ $1 \le x,y \le n$

输出格式

对于每次指令 $2$ 和 $3$，输出一个答案。

样例 #1

样例

5 4
1 2 1
2 1
2 2
3 1

1
1
2

提示

最开始，集合为 $\{1\}\{2\}\{3\}$。

1. 执行第一条指令之后，集合为 $\{1,2\}\{3\}$。
2. 此时查询 $1$ 所属集合的代表元素 $p = \min(1,2) = 1$，因此答案为 $1$。
3. 此时查询 $2$ 所属集合的代表元素 $p = \min(1,2) = 1$，因此答案为 $1$。
4. 此时查询 $1$ 所属集合大小为 $2$，因此答案为 $2$。