Road Removal#2824
You are given a network consisting of cities and bidirectional roads connecting these cities. The first cities are considered important. You need to remove the minimum number of roads such that the remaining network contains no cycles that pass through any important city. A cycle is a sequence of at least three different cities such that every pair of consecutive cities in the sequence is connected by a road, and the first and last cities are also connected by a road.
The first line contains the number of test cases (1 \le t \le 20).
Each test begins with a line containing three integers , , and (1 \le n \le 10000, 1 \le m \le 50000, 1 \le k \le n) — the number of cities, the number of roads, and the number of important cities, respectively. The cities are numbered from to n-1, and the important cities are numbered from to k-1. Each of the next lines contains two integers a_i and b_i (0 \le i < m), representing two different cities connected by a road.
It is guaranteed that 0 \le a_i, b_i < n and a_i \ne b_i. There can be at most one road between any two cities.
For each test case, numbered from to , print "Case #i: " followed by a single integer — the minimum number of roads to be removed such that no cycle contains any important city.
In the first example, there are n = 5 cities and m = 7 roads. Cities and are important. It is possible to remove the roads and , after which the remaining network will not contain any cycles that pass through important cities. Note that in the remaining network there may still be cycles that include only non-important cities. There are multiple ways to remove two roads and satisfy the conditions of the problem. Removing only one road is not sufficient to destroy all cycles involving important cities.
1-nji mysal