Train Fare

The country of JOI has $N$ cities, numbered $1$ through $N$. City $1$ is the capital.

JOI has exactly one railway company, and that company runs $M$ lines, numbered $1$ through $M$. Line $i$ ($1 \le i \le M$) connects city $U_i$ and city $V_i$ in both directions. There is no way to travel between cities other than by rail. Every city is reachable from every other city by riding one or more lines.

At the moment every line charges a fare of 1 yen. The company is in financial trouble, so it has drawn up a plan to raise the fare on some lines over the next $Q$ years. At the start of year $j$ ($1 \le j \le Q$) of the plan, the fare of line $R_j$ goes up from 1 yen to 2 yen. A fare that has been raised stays at 2 yen from then on and is never raised again.

The company surveys the residents of each city once a year. Before the plan starts, the residents of every city are satisfied with the company, but a fare increase can make some residents unhappy.

Each year's survey is taken after that year's increase. The survey in year $j$ ($1 \le j \le Q$) is therefore taken in the state where exactly the lines $R_1, R_2, \dots, R_j$ have been raised and no other line has. In the year $j$ survey, a resident of city $k$ ($2 \le k \le N$) is unhappy with the company if and only if the following condition holds.

• The minimum cost of travelling from city $k$ to the capital, city $1$, under the fares in force at that time is larger than the minimum cost of travelling from city $k$ to city $1$ under the fares in force before the plan started.

The cost of a trip that uses several lines is the sum of the fares of those lines. Residents of city $1$ are never unhappy with the company. Note that a route achieving the minimum cost under the raised fares may differ from a route achieving the minimum cost before the plan started.

Given the railway lines of JOI and the fare increase plan, write a program that reports, for each survey, the number of cities that contain unhappy residents.

Read the following data from standard input.

• The first line contains three integers $N$, $M$, $Q$ separated by spaces. JOI has $N$ cities and $M$ lines, and the fare increase plan runs for $Q$ years.
• Each of the next $M$ lines contains two integers. Line $i$ of them ($1 \le i \le M$) contains $U_i$ and $V_i$ separated by a space, meaning that line $i$ connects city $U_i$ and city $V_i$.
• Each of the next $Q$ lines contains one integer. Line $j$ of them ($1 \le j \le Q$) contains $R_j$, meaning that the fare of line $R_j$ is raised in year $j$ of the plan.

Print $Q$ lines to standard output. Line $j$ ($1 \le j \le Q$) must contain the number of cities that contain unhappy residents in the year $j$ survey.

• $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 \ne V_i$ ($1 \le i \le M$)
• $1 \le R_j \le M$ ($1 \le j \le Q$)
• $R_j \ne R_k$ ($1 \le j < k \le Q$)
• At most one line directly connects any two cities.
• Every city can reach city $1$ by using one or more lines.