AT_abc264_e [ABC264E] Blackout 2

题目描述

在某个国家有 $N$ 个城市和 $M$ 个发电站。它们统称为“地点”。
每个地点编号为 $1,2,\dots,N+M$，其中城市编号为 $1,2,\dots,N$，发电站编号为 $N+1,N+2,\dots,N+M$。

这个国家有 $E$ 条电线，第 $i$ 条电线（$1 \leq i \leq E$）连接地点 $U_i$ 和地点 $V_i$，且是双向的。
如果某个城市可以通过若干条电线到达至少一个发电站，则称该城市“有电”。

现在会发生 $Q$ 个事件。第 $i$ 个事件（$1 \leq i \leq 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$ 个事件结束后有电的城市数量。

输入输出样例 #1

输入 #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 \leq N, M$
• $N+M \leq 2 \times 10^5$
• $1 \leq Q \leq E \leq 5 \times 10^5$
• $1 \leq U_i < V_i \leq N+M$
• 若 $i \neq j$，则 $U_i \neq U_j$ 或 $V_i \neq V_j$
• $1 \leq X_i \leq E$
• $X_i$ 互不相同

样例说明 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$。

由 ChatGPT 4.1 翻译