← 返回题目列表

AtCoder · abc264_e

H. 停电 2

中文机器翻译题面 查看原题

分数: 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 城市仍然电气化。