Problem Description

In the Kingdom of JOI, there are $N$ cities numbered $1, 2, \ldots, N$. City $1$ is the capital of the kingdom.

There is only one railway company in the Kingdom of JOI, which operates $M$ routes. Each route is numbered $1, 2, \ldots, M$, and the $i$-th route ($1 \leq i \leq M$) connects city $U_i$ and city $V_i$ bidirectionally. It is not possible to travel between cities using any means other than the railway. Furthermore, it is guaranteed that any city can be reached from any other city by transferring through several routes.

Currently, the fare for each route is $1$ yen. The railway company, struggling with financial difficulties, has planned to increase the fares for some routes over the next $Q$ years. According to this plan, at the beginning of the $j$-th year ($1 \leq j \leq Q$) from the start of the plan, the fare for route $R_j$ will be increased from $1$ yen to $2$ yen. The increased fare will remain at $2$ yen thereafter and will not be increased again.

Incidentally, the railway company conducts a satisfaction survey among the residents of each city every year. Before the plan starts, all residents are satisfied with the railway company. However, the fare increases may lead to dissatisfaction among the residents.

Each year's satisfaction survey is conducted after the fare increases for that year. Therefore, the satisfaction survey for the $j$-th year ($1 \leq j \leq Q$) is conducted under the condition that the fare increases for routes $R_1, R_2, \ldots, R_j$ have been completed, and no other routes have had their fares increased. In the $j$-th year's satisfaction survey, the residents of city $k$ ($2 \leq k \leq N$) will be dissatisfied with the railway company if and only if the following condition is met:

• The minimum cost to travel from city $k$ to the capital city $1$ at the current fares is greater than the minimum cost to travel from city $k$ to city $1$ at the fares before the plan started.

Note that the cost of traveling using several routes is the sum of the fares for each route. Also, the residents of city $1$ will never be dissatisfied with the railway company. Note that the route that achieves the minimum cost after the fare increases may differ from the route that achieved the minimum cost before the plan started.

Prior to the implementation of the plan, we want to calculate the number of cities with residents who will be dissatisfied with the railway company in each of the $Q$ years' satisfaction surveys.

Input Format

Read the input from standard input in the following format:

• The first line contains three integers $N, M, Q$ separated by spaces. These represent that there are $N$ cities, $M$ routes, and the fare increase plan spans $Q$ years.
• The next $M$ lines contain two integers $U_i, V_i$ separated by spaces. These indicate that the $i$-th route connects city $U_i$ and city $V_i$.
• The next $Q$ lines contain one integer $R_j$. This indicates that in the $j$-th year of the plan, the fare for route $R_j$ will be increased.

Output Format

Output $Q$ lines to standard output. The $j$-th line ($1 \leq j \leq Q$) should contain the number of cities with residents who will be dissatisfied with the railway company in the $j$-th year's satisfaction survey.

Sample Input and Output

Sample Input #1

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

Sample Output #1

0
2
2
4
4

Sample Input #2

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

Sample Output #2

1
1
2
2
3
3

Sample Input #3

2 1 1
1 2
1

Sample Output #3

1

Notes/Hints

Task

Given the information about the railway routes in the Kingdom of JOI and the fare increase plan, create a program that calculates the number of cities with residents who will be dissatisfied with the railway company in each of the satisfaction surveys.

Constraints

All input data satisfies the following conditions:

• $2 \leq N \leq 100,000$.
• $1 \leq Q \leq M \leq 200,000$.
• $1 \leq U_i \leq N$ ($1 \leq i \leq M$).
• $1 \leq V_i \leq N$ ($1 \leq i \leq M$).
• $U_i \neq V_i$ ($1 \leq i \leq M$).
• $1 \leq R_j \leq M$ ($1 \leq j \leq Q$).
• $R_j \neq R_k$ ($1 \leq j < k \leq Q$).
• No two cities are directly connected by more than one route.
• Any city can be reached from city $1$ using several routes.

Subtasks

Subtask 1 [12 points]

Satisfies the following conditions:

• $N \leq 100$.
• $M \leq 4,950$.
• $Q \leq 30$.

Subtask 2 [14 points]

• $Q \leq 30$.

Subtask 3 [35 points]

• The correct output contains integers that appear in at most 50 different values.

Subtask 4 [39 points]

No additional constraints.

见题面 Input 部分

见题面 Output 部分