City Connectivity after Removal

A country has n cities and m roads. The m roads connect the n cities so that any two cities are reachable via some sequence of roads. There may be multiple roads between two different cities, but no road connects a city to itself.

Each city has an importance value a_i where a_i = 0 means the city does not need special development and a_i = 1 means the city needs to be specially developed. Initially, all a_i are 0.

The country will perform q planning operations. In each operation a city x is chosen and its value is flipped (i.e. a_x = 1 - a_x).

After each planning operation, as the chief planner you must determine the number of cities p which satisfy the following:

• a_p = 0 (i.e. the city is not selected for development) and
• If city p hypothetically disappears (together with all roads directly attached to it), then in the remaining graph every pair of cities u and v with a_u = a_v = 1 is connected by some path (the path may go through cities regardless of their importance).

Note: The planning operations are only hypothetical; the country’s map remains unchanged between operations.

Mathematical Formulation: Let G be the graph with cities as vertices. For a candidate city p with a_p=0, let G \ {p} denote the graph after removing p and all edges incident to p. The candidate is valid if for every pair u, v with a_u = a_v = 1, there exists a path in G \ {p} connecting u and v.

You are to output the number of valid candidate cities after each of the q operations.

inputFormat

The first line contains two integers n and m — the number of cities and roads.

The next m lines each contain two integers u and v, indicating that there is a road connecting cities u and v.

The next line contains an integer q — the number of planning operations.

Each of the next q lines contains one integer x, which is the city whose importance value is flipped.

Note: Cities are numbered from 1 to n. Initially, all a_i=0.

outputFormat

For each planning operation, output a single integer — the number of cities p (with a_p=0) that, if removed from the country (along with their incident roads), leave all cities with a=1 connected (directly or indirectly). If there are fewer than two developed cities, output the total number of cities with a=0.

sample

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

3
2
3

</p>