题目描述

$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$ 行に $1$ つずつ、順に出力せよ。

题目大意

$N$ 个学生，学生 $i$ 属于班级 $C_i$，学生们会组成一个个集合（不一定同班）。

初始每位学生所属集合只包含自己，有 $Q$ 次操作：

1 a b 合并 $a$ 和 $b$ 所在的集合（在同一集合里则什么也不发生）。

2 x y 问 $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$
• 入力はすべて整数

Sample Explanation 1

$3$ 番目のクエリの時点で、生徒 $1$ は、生徒 $2,5$ と合流しています。生徒 $1,2,5$ のうちクラス $1$ に属する生徒は $2$ 人です。 $5$ 番目のクエリの時点で、生徒 $3$ は、生徒 $4$ と合流しています。生徒 $3,4$ のうちクラス $4$ に属する生徒は $0$ 人です。

Sample Explanation 2

すでに同じ集団に属している生徒に対して、1 a b のクエリが与えられることもあります。