Jester in danger
Description
In the kingdom of Graphland, there are $N$ cities, identified by consecutive integers from $1$ to $N$, inclusive. Graphland is a very peculiar kingdom because it has two capitals: City $1$ is the royal capital of Graphland, and City $N$ is the constitutional capital.
In Graphland, there are also $M$ bidirectional roads. Each road directly connects exactly two different cities. The $i$-th road connects cities $A_i$ and $B_i$.
Let's call $G_0$ to the map of Graphland, with its $N$ cities and $M$ roads. In order to prepare contingency plans and increase the security of the kingdom, the king is interested in studying what would happen if the kingdom were to lose cities successively as a result of possible catastrophes. In the hypothetical scenario that the king wants to study, $K$ cities will be eliminated in order, one after another: $C_1, C_2, \ldots, C_K$. Starting with the map $G_0$, after each city is eliminated, the new maps $G_1, G_2, \ldots, G_K$ are obtained, respectively. In other words, $G_i$ is obtained by removing city $C_i$ (along with any road that connects to that city) from map $G_{i-1}$, for each $1 \leq i \leq K$. None of the eliminated cities will be a capital.
For each $0 \leq i \leq K$, a capital path in $G_i$ is a sequence of cities in map $G_i$ that starts at city $1$, ends at city $N$, and such that consecutive cities in the sequence are directly connected by a road. The length of a capital path is the number of cities in the sequence. If there exists a capital path in $G_i$, the king defines $D(i)$ as the minimum length among all capital paths in $G_i$. It is known that there exists a capital path in $G_0$, so $D(0)$ is defined.
For each $0 \leq i \leq K$, the king says that $G_i$ is broken if there is no capital path in $G_i$, or if there is one but $D(i) > D(0)$, meaning that the minimum length of a capital path in map $G_i$ is strictly greater than in $G_0$.
For each $0 \leq i \leq K$ such that $G_i$ is not broken, the king says that a city $v$ ($2 \leq v \leq N-1$) in map $G_i$ is critical if the map obtained by removing $v$ from $G_i$ would be broken.
You are a jester in the king's court, and unfortunately, you are also the only person in the entire kingdom who knows how to code. To avoid the punishment of the relentless king of Graphland, you must write a program that, for each $0 \leq i \leq K$, determines the number of critical cities in map $G_i$, or indicates that $G_i$ is broken.
The first line contains three integers $N$, $M$, $K$ ($3 \leq N \leq 10^5$, $1 \leq M \leq 2 \cdot 10^5$, $1 \leq K \leq N-2$).
Then $M$ lines describe the roads. The $i$-th line contains two integers $A_i$ and $B_i$ ($1 \leq A_i < B_i \leq N$). These $M$ lines are all distinct.
Then $K$ lines contain the cities to be eliminated, in the order they are eliminated. That is, the $i$-th line contains the integer $C_i$ ($2 \leq C_i \leq N-1$). These $K$ cities are all distinct.
A single line with $K+1$ integers, indicating what the king requested for each map.
More precisely, for each $0 \leq i \leq K$, the $i$-th integer (counting from $0$) should be:
- $-1$, if map $G_i$ is broken
- The number of critical cities in map $G_i$, if map $G_i$ is not broken
Input
The first line contains three integers $N$, $M$, $K$ ($3 \leq N \leq 10^5$, $1 \leq M \leq 2 \cdot 10^5$, $1 \leq K \leq N-2$).
Then $M$ lines describe the roads. The $i$-th line contains two integers $A_i$ and $B_i$ ($1 \leq A_i < B_i \leq N$). These $M$ lines are all distinct.
Then $K$ lines contain the cities to be eliminated, in the order they are eliminated. That is, the $i$-th line contains the integer $C_i$ ($2 \leq C_i \leq N-1$). These $K$ cities are all distinct.
Output
A single line with $K+1$ integers, indicating what the king requested for each map.
More precisely, for each $0 \leq i \leq K$, the $i$-th integer (counting from $0$) should be:
- $-1$, if map $G_i$ is broken
- The number of critical cities in map $G_i$, if map $G_i$ is not broken
4 5 2
1 2
2 4
2 3
1 3
3 4
3
2
6 5 2
1 2
2 3
2 5
3 5
3 6
4
5
5 5 3
1 2
3 4
1 3
4 5
2 5
2
4
3
0 1 -1
2 2 2
1 -1 -1 -1
Note
- In the first example, the capital paths of minimum length in $G_0$ are $1 \rightarrow 2 \rightarrow 4$ and $1 \rightarrow 3 \rightarrow 4$. If a non-capital city, either $2$ or $3$, were to be eliminated, there would still be at least one capital path with the same minimum length, so there are no critical cities in $G_0$. In $G_1$, city $3$ has already been eliminated, so if city $2$ were to be eliminated in $G_1$, there would be no remaining path between capitals and the map would be broken. For this reason, city $3$ is critical in $G_1$, and there is exactly one critical city in $G_1$. Finally, in $G_2$, both cities (2 and 3) have been eliminated and there are no remaining capital paths, so $G_2$ is broken.
- In the second example, $2$ and $3$ are the only critical cities in $G_0, G_1$, and $G_2$.
- In the third example, $2$ is the only critical city in $G_0$, and $G_1,G_2,G_3$ are broken. Note that in $G_1$ there exists a capital path $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$, but its length (and the length of any other) is greater than the capital path of minimum length in $G_0$, which is $1 \rightarrow 2 \rightarrow 5$.