Blackout 2

题目描述

一个国家有 $N$ 个城市和 $M$ 座发电厂，统称为地点。
这些地点编号为 $1,2,\dots,N+M$，其中地点 $1,2,\dots,N$ 是城市，地点 $N+1,N+2,\dots,N+M$ 是发电厂。
这个国家有 $E$ 条输电线。输电线 $i$（$1 \le i \le E$）双向连接地点 $U_i$ 和地点 $V_i$。
如果可以通过若干条输电线从某城市到达至少一座发电厂，则该城市被称为通电。 现在会发生 $Q$ 次事件。在第 $i$ 次（$1 \le i \le Q$）事件中，输电线 $X_i$ 断裂，变得不可用。输电线一旦断裂，在随后的事件中仍然保持断裂状态。 求每次事件发生后通电的城市数量。

输入格式

输入从标准输入按如下格式给出： $N$ $M$ $E$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_E$ $V_E$ $Q$ $X_1$ $X_2$ $\vdots$ $X_Q$

输出格式

输出 $Q$ 行。
第 $i$ 行应包含第 $i$ 次事件发生后通电的城市数量。

5 5 10
2 3
4 10
5 10
6 9
2 9
4 8
1 7
3 6
8 10
1 8
6
3
5
8
10
2
7

4
4
2
2
2
1

提示

输入中的所有数值均为整数。 $1 \le N,M$ $N+M \le 2 \times 10^5$ $1 \le Q \le E \le 5 \times 10^5$ 1 \le U_i < V_i \le N+M 若 $i \neq j$，则 $U_i \neq U_j$ 或 $V_i \neq V_j$。 $1 \le X_i \le E$ $X_i$ 互不相同。最初，所有城市都是通电的。

第 $1$ 次事件断裂了连接点 $5$ 和点 $10$ 的输电线 $3$。 现在城市 $5$ 不再通电，而仍有 4 个城市保持通电。

第 $2$ 次事件断裂了连接点 $2$ 和点 $9$ 的输电线 $5$。 第 $3$ 次事件断裂了连接点 $3$ 和点 $6$ 的输电线 $8$。 现在城市 $2$ 和 $3$ 不再通电，而仍有 2 个城市保持通电。

第 $4$ 次事件断裂了连接点 $1$ 和点 $8$ 的输电线 $10$。 第 $5$ 次事件断裂了连接点 $4$ 和点 $10$ 的输电线 $2$。 第 $6$ 次事件断裂了连接点 $1$ 和点 $7$ 的输电线 $7$。 现在城市 $1$ 不再通电，而仍有 1 个城市保持通电。

标签: AtCoder|abc264E

来源

AtCoder|abc264E