Rebel Galaxy: Resistance Connectivity

A long time ago, in a distant galaxy, an evil empire ruled using its superweapon. By a twist of fate, a rebel group destroyed the empire’s superweapon and captured nearly all the planets. These planets were originally connected by special ether tunnels, either directly or indirectly. However, when the empire rebuilt its superweapon, it launched attacks on the rebel-held planets. As planets get destroyed, the existing ether tunnels (edges) between the remaining planets become unreliable.

You are given the original connectivity of the planets via ether tunnels along with the order in which the empire attacks the planets. After each attack (i.e. removal of a planet and its adjacent tunnels), compute the number of connected components among the planets still held by the rebels. Two planets are in the same connected component if there exists a path connecting them. Formally, for any planets \(u\) and \(v\), they belong to the same component if there exists a sequence \(u = u_1, u_2, \dots, u_k = v\) such that for each \(i = 1, 2, \dots, k-1\), an ether tunnel connects \(u_i\) to \(u_{i+1}\).

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of planets and the number of ether tunnels.

The next \(m\) lines each contain two integers \(u\) and \(v\) indicating there is an ether tunnel connecting planet \(u\) and planet \(v\) (the connection is bidirectional).

The following line contains a single integer \(k\) which denotes the number of attacks.

The next \(k\) lines each contain one integer, representing the index of the planet being attacked in that order. Planets are numbered from 1 to \(n\).

outputFormat

Output \(k\) lines, where the \(i\)th line contains the number of connected components among the remaining planets after the \(i\)th attack.

sample

5 4
1 2
2 3
3 4
4 5
3
3
1
5

2
2
2