分数: 500 点
问题陈述
一个国家有 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-th (1 \le i \le Q) 事件,电源线 X_i 损坏,使其无法使用。 一旦电源线断裂,在随后的事件中它仍然是断线的。
查找每次事件发生后电气化城市的数量。
约束
- 输入中的所有值都是整数。
- 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
- If i \neq j,然后 U_i \neq U_j or V_i \neq V_j.
- 1 \le X_i \le E
- 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第一个事件。
示例输入 1
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
示例输出 1
4 4 2 2 2 1
最初,所有城市都实现电气化。
- 的 1-st 事件破坏了电源线
连接点的 3 连接点 5 和点 10.
- 现在城市 5 不再带电,而 4 城市仍然电气化。
- 的 2-nd 事件破坏了电源线 5 连接点 2 和点 9.
- 的 3-rd 事件破坏了电源线 8 连接点 3 和点 6.
- 现在城市 2 和 3 不再带电,而 2 城市仍然电气化。
- 的 4第一个事件破坏了电源线 10 连接点 1 和点 8.
- 的 5第一个事件破坏了电源线 2 连接点 4 和点 10.
- 的 6第一个事件破坏了电源线 7 连接点 1 和点 7.
- 现在城市 1 不再带电,而 1 城市仍然电气化。