停电 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$ 个事件断开了连接场所 $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$ 个城市通电。

数据范围

• 输入中的所有值均为整数。
• $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 \lt 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$ 两两不同。