AT_abc391_c.[ABC391C] Pigeonhole Query

有 $N$ 只鸽子，编号为 $1$ 至 $N$。另有 $N$ 个鸽巢，编号为 $1$ 至 $N$。初始时，鸽子 $i$ 位于巢 $i$ 中（$1 \leq i \leq N$）。

请依次处理 $Q$ 个查询。查询有两种类型，以下列形式给出：

• 1 P H：将鸽子 $P$ 移动到巢 $H$。
• 2：输出包含多只鸽子的鸽巢数量。

输入通过标准输入按以下格式给出：

$N$ $Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个查询为以下两种形式之一：

$1$ $P$ $H$
$2$

根据题目要求，按顺序输出每个查询的答案，每个答案占一行。

约束条件

• $2 \leq N \leq 10^6$
• $1 \leq Q \leq 3 \times 10^5$
• $1 \leq P, H \leq N$
• 对于类型 1 的查询，移动前鸽子 $P$ 不在巢 $H$ 中
• 输入均为整数

样例解释 1

初始时，鸽子 $1,2,3,4$ 分别位于巢 $1,2,3,4$。

• 第 $1$ 个查询：巢 $1,2,3,4$ 中分别有 $1,1,1,1$ 只鸽子。没有包含多只鸽子的巢，输出 $0$。
• 第 $2$ 个查询：将鸽子 $1$ 移动到巢 $2$。
• 第 $3$ 个查询：巢 $1,2,3,4$ 中分别有 $0,2,1,1$ 只鸽子。包含多只鸽子的巢为巢 $2$，输出 $1$。
• 第 $4$ 个查询：将鸽子 $3$ 移动到巢 $2$。
• 第 $5$ 个查询：巢 $1,2,3,4$ 中分别有 $0,3,0,1$ 只鸽子。包含多只鸽子的巢为巢 $2$，输出 $1$。
• 第 $6$ 个查询：将鸽子 $3$ 移动到巢 $4$。
• 第 $7$ 个查询：巢 $1,2,3,4$ 中分别有 $0,2,0,2$ 只鸽子。包含多只鸽子的巢为巢 $2$ 和 $4$，输出 $2$。

翻译由 DeepSeek R1 完成