{"raw_statement":[{"iden":"statement","content":"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.\n\nGiven 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.\n\nThere will be Q queries each with a K. Each query is independent _i.e._ you have to consider the original graph for each query.\n\nFirst 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.\n\nFor each query output the maximum number of bridges you can kill.\n\nAdding the edge  removes the existing 2 bridges.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"For each query output the maximum number of bridges you can kill."},{"iden":"note","content":"Adding the edge  removes the existing 2 bridges."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected, unweighted, connected graph with $ |V| = N $, $ |E| = M $.  \nLet $ B \\subseteq E $ be the set of bridges in $ G $.  \nLet $ \\mathcal{E} $ be the set of all possible non-existing edges (i.e., $ \\binom{V}{2} \\setminus E $).  \n\n**Constraints**  \n1. $ 1 \\le N, Q \\le 10^5 $  \n2. $ 0 \\le M \\le 2 \\cdot 10^5 $  \n3. For each query, $ 1 \\le K \\le M $  \n4. Each query is independent; graph reverts to original before each query.  \n\n**Objective**  \nFor each query with parameter $ K $, determine the **maximum number of bridges that can be eliminated** by adding at most $ K $ edges from $ \\mathcal{E} $.  \n\nLet $ f(K) $ denote the maximum number of bridges removable by adding $ \\le K $ edges.  \nOutput $ f(K) $ for each query.","simple_statement":"Given a connected undirected graph with N nodes and M edges, for each query with K, add at most K new edges to minimize the number of bridges. Output the maximum number of bridges you can remove.","has_page_source":false}