In the country of JOI, there are $N$ cities, numbered $1, 2, \dots, N$. City $1$ is the capital of JOI.

There is only one railway company in JOI, which operates $M$ railway lines. These lines are numbered $1, 2, \dots, M$. The $i$-th line ($1 \le i \le M$) connects city $U_i$ and city $V_i$ in both directions. It is not possible to travel between cities except by railway. Also, it is possible to travel from any city to any other city by changing trains across several lines.

Currently, the fare for every line is $1$ yen. Due to poor business performance, the railway company has planned to raise the fares of some lines over the next $Q$ years. In this plan, at the beginning of the $j$-th year ($1 \le j \le Q$) from the start of the plan, the fare of line $R_j$ will be raised from $1$ yen to $2$ yen. Once a line's fare is raised, it will remain $2$ yen forever and will not be raised again.

The railway company conducts a satisfaction survey of the residents of each city every year. Before the start of the plan, residents of all cities are satisfied with the railway company, but the fare increases may cause some residents to become dissatisfied.

The satisfaction survey for each year is conducted after the fare increase for that year has been implemented. Therefore, the satisfaction survey in the $j$-th year ($1 \le j \le Q$) is conducted in a state where the fare increases for lines $R_1, R_2, \dots, R_j$ have been completed, and the fares of other lines have not been raised. In the satisfaction survey of the $j$-th year ($1 \le j \le Q$), the residents of city $k$ ($2 \le k \le N$) are 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 start of the plan.

Note that the cost of traveling using several lines is the sum of the fares of each line. Also, residents of city $1$ are never dissatisfied with the railway company. Note that the path that achieves the minimum cost with the fares after the increases may be different from the path that achieves the minimum cost with the fares before the start of the plan.

Prior to the execution of the plan, you want to calculate the number of cities where residents are dissatisfied with the railway company for each of the satisfaction surveys over the next $Q$ years.

Task

Given information about the railway lines in JOI and the fare increase plan, write a program that calculates the number of cities where residents are dissatisfied with the railway company in each satisfaction survey.

Input

Read the following from standard input:

• The first line contains three space-separated integers $N, M, Q$. These represent that there are $N$ cities and $M$ railway lines in JOI, and the fare increase plan spans $Q$ years.
• The $i$-th line of the following $M$ lines ($1 \le i \le M$) contains two space-separated integers $U_i, V_i$. These represent that the $i$-th line connects city $U_i$ and city $V_i$.
• The $j$-th line of the following $Q$ lines ($1 \le j \le Q$) contains an integer $R_j$. This represents that the fare of line $R_j$ will be raised in the $j$-th year of the plan.

Output

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

Constraints

All input data satisfies the following conditions:

• $2 \le N \le 100\,000$.
• $1 \le Q \le M \le 200\,000$.
• $1 \le U_i \le N$ ($1 \le i \le M$).
• $1 \le V_i \le N$ ($1 \le i \le M$).
• $U_i \neq V_i$ ($1 \le i \le M$).
• $1 \le R_j \le M$ ($1 \le j \le Q$).
• $R_j \neq R_k$ ($1 \le j < k \le Q$).
• For any two cities, there is at most one line connecting them directly.
• For any city, it is possible to travel from that city to city $1$ using several lines.

Subtasks

Subtask 1 [12 points]

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

Subtask 2 [14 points]

• $Q \le 30$.

Subtask 3 [35 points]

• The number of distinct integers appearing in the correct output is $50$ or less.

Subtask 4 [39 points]

• No additional constraints.

Examples

Input 1

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

Output 1

0
2
2
4
4

Note

In this example, the fares from each city to city $1$ before the start of the plan and at the time of each satisfaction survey are as follows:

For example, in the 3rd year's satisfaction survey, residents of city 3 and city 5 are dissatisfied, so output 2 on the 3rd line.

Input 2

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

Output 2

1
1
2
2
3
3

Input 3

2 1 1
1 2
1

Output 3

1