Description

A long time ago, in a galaxy far away, a dark empire ruled the entire galaxy with its superweapon.

One day, by a stroke of chance, a rebel force destroyed the empire’s superweapon and captured almost all the planets in the galaxy. These planets are directly or indirectly connected through special “aether” tunnels.

But the good times did not last. Soon, the empire rebuilt its superweapon. With its power, the empire began systematically destroying the planets occupied by the rebels. As more planets were destroyed, the communication channels between planets also became unreliable.

Now, the leader of the rebels assigns you a task: given the original connectivity of the “aether” tunnels between planets and the order in which the empire attacks the planets, compute as quickly as possible the number of connected components of the planets occupied by the rebels after each strike. (If two planets can be connected directly or indirectly through the existing aether tunnels, then they are in the same connected component.)

Input Format

The first line contains two integers $n,m$, the number of planets and the number of aether tunnels. The planets are numbered by integers $0 \sim n-1$.

Each of the next $m$ lines contains two integers $x,y$, indicating there is an “aether” tunnel between planet $x$ and planet $y$, allowing direct communication.

The next line contains an integer $k$, the number of planets that will be attacked.

Each of the next $k$ lines contains one integer, listing the empire’s attack targets in order. These $k$ numbers are pairwise distinct and all lie in the range $0$ to $n-1$.

Output Format

The first line contains the number of connected components of the planets at the beginning. Each of the next $k$ lines contains one integer, the number of connected components of the remaining planets after that strike.

8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7

1
1
1
2
3
3

Hint

Constraints

For $100\%$ of the testdata, $1\le m \le 2\times 10^5$, $1\le n \le 2m$, $x \neq y$.

Translated by ChatGPT 5