鸽巢动态统计问题

题目描述

有 $N$ 只鸽子（编号 $1$ 到 $N$）和 $N$ 个巢穴（编号 $1$ 到 $N$）。初始时，每只鸽子 $i$ 位于巢穴 $i$ 中。

需要处理 $Q$ 个查询操作，操作分为两种类型：

操作类型

1. ​移动操作 1 P H

   • 将鸽子 $P$ 移动到巢穴 $H$
   • 保证移动前鸽子 $P$ ​不在巢穴 $H$ 中

2. ​统计操作 2

   • 输出当前包含多于一只鸽子的巢穴数量

输入格式

$N$ $Q$

$\mathrm{query}_1$

$\mathrm{query}_2$

$\vdots$

$\mathrm{query}_Q$

每个$query$一定是下列两种情况之一:

1 P H

2

• $2 \leq N \leq 10^6$
• $1 \leq Q \leq 3\times 10^5$
• $1 \leq P, H \leq N$
• 数据保证鸽子 $P$ 在移动之前不在鸽巢 $H$ 中.
• 所有输入数据均为整数.

输出格式

对于每一个$query$为$2$的情况,打印此时一共有多少个巢满足

$2 \leq$ 巢内鸽子数

注意换行打印

样例

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

0
1
1
2

鸽子动态操作示例1详解

初始状态

• 4只鸽子初始所在巢穴：
  鸽子1 → 巢穴1
鸽子2 → 巢穴2
鸽子3 → 巢穴3
鸽子4 → 巢穴4
• 各巢穴鸽子数量：
  [1, 1, 1, 1]

操作流程与结果

关键状态对比

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