Problem Description

In a country’s territory, there are $n$ cities and $m$ roads. These $m$ roads connect the $n$ cities, meaning that for any two cities, there is a route that can reach one from the other directly or indirectly. There may be multiple roads between the same pair of cities, but there is no road whose two ends connect to the same city.

The country wants to select some cities for key development. Specifically, each city has an importance value $a_i$, where $a_i=0$ means the city does not need key development, and $a_i=1$ means the city needs key development. Initially, all $a_i=0$.

The country performs $q$ planning operations. In each operation, a city $x$ is chosen and we set $a_x \gets 1-a_x$.

After each operation, as the chief planner, you need to find the number of cities $p$ such that $a_p=0$, and after city $p$ disappears (together with all roads directly connected to city $p$), any two cities $u,v$ with $a_u=a_v=1$ are still connected directly or indirectly.

Note that the planning is only hypothetical on paper, and no city is actually deleted.

Input Format

The first line contains three positive integers $n,m,q$ separated by spaces.

The next $m$ lines each contain two positive integers $u,v$, describing a bidirectional road connecting cities $u$ and $v$.

The next $q$ lines each contain one positive integer $x$, describing one planning operation.

Output Format

Output $q$ lines. Each line contains one non-negative integer, which is the answer after each modification.

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

3
2
3
1
3
4

Hint

Sample Explanation

Take the 4th planning operation as an example. At this time, the cities that need key development are $1$ and $4$, so the only cities with $a_p=0$ are $2$ and $3$. If city $2$ disappears, there is a path $1-3-4$. If city $3$ disappears, then $1$ and $4$ cannot reach each other. Therefore, the only city that satisfies the condition is $2$, and the answer is $1$.

Constraints

• For $15\%$ of the testdata, $n,q \le 300$, $m \le 500$.
• For another $15\%$ of the testdata, $m=n-1$, and for all roads, $v=u+1$.
• For another $20\%$ of the testdata, $m=n-1$.

For all testdata, $2 \le n \le 10^5$, $n-1\le m \le 2 \times 10^5$, $1 \le q \le 2 \times 10^5$, $1 \le u,v,x \le n$, $u \neq v$.

Translated by ChatGPT 5