A Dynamic Connectivity Problem

View as PDF

Points: 15 (partial)
Time limit: 0.6s
Java 8 1.0s
Memory limit: 162M

Problem type

A graph has vertices and edges. When a vertex is deleted, all incident edges are deleted.

Given a sequence of vertices to be deleted one by one, count the number of connected components before and after each deletion.

Constraints

All vertices are labeled from to .

Input Specification

The first line contains two space-separated integers, and .

Each of the next lines contains two space-separated integers, and , indicating that and are connected with an edge.

Next, a single integer follows on its own line, indicating the number of vertices that will be deleted.

lines follow, each indicating a vertex that is to be deleted. A vertex will be deleted at most once.

Output Specification

Output lines. On line , output the number of connected components after the first vertices have been deleted.

Sample Input

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

Sample Output

1
1
1
2
3
3