SP25684 JOLLYKINGDOM - Jolly Kingdom
题目描述
欢乐王国以其军队的力量著称。该国拥有 $N$ 支剑士部队和 $M$ 支弓箭手部队，每支部队都有其独特的战斗风格，与众不同。
邪恶的女巫已经第十次企图用她的怪物军团夺取欢乐王国的王位。根据间谍收集到的情报，女巫将在接下来的 $H$ 天内每天发动攻击。每过一天，她的怪物军团便会增加一只新怪物，这使得敌人的实力日益增强。
女巫的每只怪物都异常强大，难以击败，唯有第 $X_i$ 支剑士部队或第 $Y_i$ 支弓箭手部队能够将其击退。而当一只怪物被击败后，它将于次日复活再战。
为了保卫欢乐王国，每日都必须将所有怪物击败。然而，派遣一支部队的成本很高，因此国王希望每天仅派遣最少数量的部队，以确保当日所有怪物都能够被击败。
作为国王的顾问，你需要帮他计算出每天需派遣的部队数量。
输入格式
第一行包含三个整数：$N$、$M$ 和 $H$，分别表示剑士部队数量、弓箭手部队数量及女巫攻击的天数。
接下来的 $H$ 行中，每行包含两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 天新增的怪物只能被第 $X_i$ 支剑士部队或第 $Y_i$ 支弓箭手部队击败。
同一只怪物不会同时有相同的弱点（即对于所有 $1 \leq i < j \leq H$，不会同时满足 $X_i = X_j$ 且 $Y_i = Y_j$）。
输出格式
输出 $H$ 行，每行包含一个整数，表示相应的天数里，最少需要派遣的部队数量。
**样例**
输入：
```
4 4 9
1 1
1 2
1 3
2 1
4 1
3 4
3 3
4 3
4 4
```
输出：
```
1
1
1
2
2
3
3
4
4
```
**样例解释**
在该样例中，我们用符号表示：{ 剑士部队编号: 击败的怪物编号 } { 弓箭手部队编号: 击败的怪物编号 }
- 第 1 天：{**1**: 1} {}
- 第 2 天：{**1**: 1 2} {}
- 第 3 天：{**1**: 1 2 3} {}
- 第 4 天：{**1**: 1 2 3} {**1**: 4}
- 第 5 天：{**1**: 1 2 3} {**1**: 4 5}
- 第 6 天：{**1**: 1 2 3; **3**: 6} {**1**: 4 5}
- 第 7 天：{**1**: 1 2 3; **3**: 6 7} {**1**: 4 5}
- 第 8 天：{**1**: 1 2 3; **3**: 6 7; **4**: 8} {**1**: 4 5}
- 第 9 天：{**1**: 1 2 3; **3**: 6 7; **4**: 8 9} {**1**: 4 5}
**提示**
- 在这个问题中，$N$ 和 $M$ 均可达到 1000，因此 $H$ 可以高达 $10^6$。这意味着与原问题相比，本题的规模更大，需针对性优化输入输出方式，如使用 `scanf`/`printf` 以提高效率。
- 如果觉得此问题难以解决，可以参考类似但规模较小的问题：[原问题链接](https://jollybeeoj.com/problem/view/199)。
**本翻译由 AI 自动生成**