102644: [AtCoder]ABC264 E - Blackout 2

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.

问题描述

一个国家有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个事件之后立即通电的城市数量。

样例输入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个事件断裂连接地点5和地点10的电力线3。
• 第2个事件断裂连接地点2和地点9的电力线5。
• 第3个事件断裂连接地点3和地点6的电力线8。
• 第4个事件断裂连接地点1和地点8的电力线10。
• 第5个事件断裂连接地点4和地点10的电力线2。
• 第6个事件断裂连接地点1和地点7的电力线7。