402827: GYM100889 K Kill Bridges

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.

First line contains three integers N, M and Q(1 ≤ N, Q ≤ 10⁵ and 0 ≤ M ≤ 2 * 10⁵). 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.

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

3 2 1
1 2
2 3
1

2

Adding the edge removes the existing 2 bridges.