Increased Railway Fares and Resident Dissatisfaction

JOI Country has \(N\) cities numbered \(1,2,\ldots,N\) with city \(1\) being the capital. There are \(M\) railway lines (numbered \(1,2,\ldots,M\)) connecting the cities. The \(i\)-th railway connects cities \(U_i\) and \(V_i\), and it is guaranteed that any two cities are connected through some sequence of railways.

Initially, every railway ticket costs 1 yen. However, due to poor management, the only railway company plans to raise fares over the next \(Q\) years. At the beginning of year \(j\) (\(1\le j\le Q\)), the cost of railway \(R_j\) increases from 1 yen to 2 yen and remains 2 yen thereafter.

Every year after the fare increase (i.e. after the new price is in effect), a satisfaction survey is conducted. For each city \(k\) (\(2\le k\le N\)), let \(d_k^0\) be the minimum total fare from city \(k\) to the capital computed before any price increases, and let \(d_k^j\) be the minimum total fare in year \(j\) (after the first \(j\) fare increases). If \(d_k^j > d_k^0\), then the residents of city \(k\) become dissatisfied.

Your task is to compute, for each year from \(1\) to \(Q\), the number of cities (excluding the capital) whose residents become dissatisfied in that year.

Note that the total fare is the sum of the fares of each railway used, and switching railways is allowed.

inputFormat

The input is given as follows:

• The first line contains three integers \(N\), \(M\), and \(Q\) separated by spaces.
• The following \(M\) lines each contain two integers \(U_i\) and \(V_i\) indicating that railway line \(i\) connects cities \(U_i\) and \(V_i\).
• The next line contains \(Q\) integers \(R_1, R_2, \ldots, R_Q\); the \(j\)-th integer indicates the railway line that will have its fare increased in year \(j\).

It is guaranteed that any two cities are connected by some sequence of railways.

outputFormat

Output \(Q\) lines. The \(j\)-th line should contain one integer: the number of cities \(k\) (with \(2\le k\le N\)) for which the minimum fare from city \(k\) to the capital in year \(j\) is strictly greater than the original minimum fare (computed when all railways had a fare of 1 yen).

sample

3 3 2
1 2
2 3
1 3
1 2

1
1