K. Kill Bridges
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

CodeCraft'16 gives you the opportunity to become a killer(legally!). Subject to the constraint that you are best at your job. So you have to prove yourself.

Given an undirected, unweighted, connected graph with N vertices and M edges, you have to add at most K new edges in the graph to minimize the number of bridges.

There will be Q queries each with a K. Each query is independent i.e. you have to consider the original graph for each query.

Input

First line contains three integers N, M and Q(1 ≤ N, Q ≤ 105 and 0 ≤ M ≤ 2 * 105). Next M lines contain u and v denoting an undirected edge between u and v(1 ≤ u, v ≤ N). Next Q lines contain a single integer K(1 ≤ K ≤ M) denoting the maximum number of edges that you can add.

Output

For each query output the maximum number of bridges you can kill.

Example
Input
3 2 1
1 2
2 3
1
Output
2
Note

Adding the edge removes the existing 2 bridges.