Score : $500$ points

问题描述

一个国家拥有 $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$ 条输电线路断裂，变得无法使用。一旦输电线路断裂，在后续的事件中它将保持断裂状态。

找出每个事件发生后已通电城市的数量。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

A country has $N$ cities and $M$ power plants, which we collectively call places.
The places are numbered $1,2,\dots,N+M$, among which Places $1,2,\dots,N$ are the cities and Places $N+1,N+2,\dots,N+M$ are the power plants.

This country has $E$ power lines. Power Line $i$ ($1 \le i \le E$) connects Place $U_i$ and Place $V_i$ bidirectionally.
A city is said to be electrified if one can reach at least one of the power plants from the city using some power lines.

Now, $Q$ events will happen. In the $i$-th ($1 \le i \le Q$) event, Power Line $X_i$ breaks, making it unusable. Once a power line breaks, it remains broken in the succeeding events.

Find the number of electrified cities right after each events.

Constraints

• All values in input are integers.
• $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$, then $U_i \neq U_j$ or $V_i \neq V_j$.
• $1 \le X_i \le E$
• $X_i$ are distinct.

Input

Input is given from Standard Input in the following format:

$N$ $M$ $E$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_E$ $V_E$

$Q$

$X_1$

$X_2$

$\vdots$

$X_Q$

Output

Print $Q$ lines.
The $i$-th line should contain the number of electrified cities right after the $i$-th event.

Sample Input 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

Sample Output 1

4
4
2
2
2
1

Initially, all cities are electrified.

• The $1$-st event breaks Power Line $3$ that connects Point $5$ and Point $10$.
  • Now City $5$ is no longer electrified, while $4$ cities remain electrified.
• The $2$-nd event breaks Power Line $5$ that connects Point $2$ and Point $9$.
• The $3$-rd event breaks Power Line $8$ that connects Point $3$ and Point $6$.
  • Now Cities $2$ and $3$ are no longer electrified, while $2$ cities remain electrified.
• The $4$-th event breaks Power Line $10$ that connects Point $1$ and Point $8$.
• The $5$-th event breaks Power Line $2$ that connects Point $4$ and Point $10$.
• The $6$-th event breaks Power Line $7$ that connects Point $1$ and Point $7$.
  • Now City $1$ is no longer electrified, while $1$ city remains electrified.

update @ 2024/3/10 11:09:44