Description

In addition to a submarine high-speed rail connecting mainland China, Taiwan, and Japan, Boai (博艾) City also has a well-developed urban rail transit system. We can model the Boai metro system as an undirected connected graph. There are $N$ metro stations and $M$ short rail segments, each connecting two different stations.

The fare policy is simple. From station A to station B, for each short segment traversed (i.e., an edge connecting two adjacent stations), the charge is $1$ Boai yuan. That is, different paths from A to B may have different fares.

Assume Fanhua High School (凡华中学) is at station $1$. Students commute by metro, and they know that taking a shortest path yields the cheapest fare.

However, the Boai metro company has been operating at a loss and plans to raise fares. One price increase changes the charge for a short segment from $1$ to $2$. The same segment will not be increased more than once. They will perform $Q$ such increases.

Students know that if a segment on one of their shortest paths is increased, they can change their route so that the total fare remains unchanged. However, as more and more segments are increased, when students living near some station find that, after the increases, there is no way to travel from home to school with a total fare equal to the initial fare, they become dissatisfied.

Now the metro company wants to know, for each price increase, how many stations will have students who become dissatisfied due to the increase.

Input Format

The first line contains three integers $N, M, Q$.

The next $M$ lines each contain $2$ integers $a_i, b_i$, indicating that the $i$-th rail segment connects these two stations. The integer $i$ is the segment index.

The next $Q$ lines each contain one integer $r_j$, indicating the index of the rail segment increased at step $j$.

Output Format

Output $Q$ lines. Each line contains one integer, the number of dissatisfied stations.

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

0
2
2
4
4

Hint

Sample Explanation

次数 车站2 车站3 车站4 车站5
初始 1     1     2     2
1    1     1     2     2
2    1     2     2     3
3    1     2     2     3
4    2     2     3     3
5    2     2     4     3

Constraints

• For $20\%$ of the testdata, $N \le 100, Q \le 30$.
• For $40\%$ of the testdata, $Q \le 30$.
• For $70\%$ of the testdata, there are no more than $50$ distinct integers in the correct outputs (data range spoiler series).
• For $100\%$ of the testdata, $N \le 100000, Q \le M \le 200000$.

Translated by ChatGPT 5