当前没有测试数据。

E - Blackout 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$ 个事件 ($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$
• 如果 $i \neq j$，则 $U_i \neq U_j$ 或 $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$ 个事件后通电城市的数量。

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$ 个事件断掉了连接地点 $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$ 个城市仍然通电。