402827: GYM100889 K Kill Bridges
Description
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.
InputFirst 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.
OutputFor each query output the maximum number of bridges you can kill.
ExampleInput3 2 1Output
1 2
2 3
1
2Note
Adding the edge removes the existing 2 bridges.