402827: GYM100889 K Kill Bridges

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Kill Bridgestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

ExampleInput
3 2 1
1 2
2 3
1
Output
2
Note

Adding the edge removes the existing 2 bridges.

加入题单

上一题 下一题 算法标签: