问题陈述

有 $N$ 只鸽子，编号从 $1$ 到 $N$ ，有 $N$ 个鸽巢，编号从 $1$ 到 $N$ 。最初，鸽子 $i$ 在 $1\leq i\leq N$ 的巢 $i$ 中。

您会收到 $Q$ 个操作，您必须按顺序处理这些操作。操作有两种类型，每种都以下列格式之一给出：

• 操作1： 1 P H : 将鸽子 $P$ 移至鸽巢 $H$ 。
• 操作2： 2 : 输出包含一只以上鸽子的鸽巢数量。

输入格式

第一行包含两个整数，$N$ 和 $Q$ 分别代表鸽子鸽巢的数量和查询次数；
接下来的$Q$行，每行包含一个操作。

输出格式

若干行，每行输出所有 操作2 所查询的鸽巢数量。

4 7
2
1 1 2
2
1 3 2
2
1 3 4
2

0
1
1
2

最初，鸽子 $1,2,3,4$ 分别在鸽巢 $1,2,3,4$ 中。

• 对于第 1 次操作，鸽巢 $1,2,3,4$ 中的鸽子数量为 $1,1,1,1$ 。没有鸽巢包含多只鸽子，输出为 $0$ 。
• 对于第 2 个操作，将鸽子 $1$ 移至鸽巢 $2$ 。
• 对于第 3 次操作，计数分别变为 $0,2,1,1$ 。一个鸽巢（巢 $2$ ）包含多羽鸽子，因此输出 $1$ 。
• 对于第 4 次操作，将鸽子 $3$ 移至鸽巢 $2$ 。
• 对于第 5 次操作，计数分别变为 $0,3,0,1$ 。一个巢（巢 $2$ ）包含多羽鸽子，因此输出 $1$ 。
• 对于第 6 次操作，将鸽子 $3$ 移至鸽巢 $4$ 。
• 对于第 7 次操作，计数分别变为 $0,2,0,2$ 。有两个鸽巢（ $2$ 和 $4$ ）包含多羽鸽子，因此输出 $2$ 。

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

0
1
2
1

数据范围

对于$50\%$的数据，

• $2 \leq N \leq 10^3$
• $1 \leq Q \leq 1\times 10^3$

对于$100\%$的数据，

• $2 \leq N \leq 10^6$
• $1 \leq Q \leq 3\times 10^5$
• $1 \leq P, H \leq N$
• 对于第一种类型的操作，鸽子 $P$ 在移动之前不在鸽巢 $H$ 中。
• 所有输入值均为整数。