Problem K
Flying Safely
![\includegraphics[width=0.37\textwidth ]{cartoon}](/problems/flyingsafely/file/statement/en/img-0001.jpg)
To limit the trust issues you are asked for help. Given the flight schedule, figure out the smallest set of pilots that need to be trusted, such that the spy can safely travel between all cities.
Input
On the first line one positive number: the number of test cases, at most 100. After that per test case:
-
one line with two space-separated integers $n$ ($2\le n \le 1\, 000$) and $m$ ($1\le m \le 10\, 000$): the number of cities and the number of pilots, respectively.
-
$m$ lines with two space-separated integers $a$ and $b$ ($1 \le a,b \le n, a \neq b$): a pilot flying his plane back and forth between city $a$ and $b$.
It is possible to go from any city to any other city using one or more flights. In other words: the graph is connected.
Output
Per test case:
-
one line with one integer: the minimum number of pilots that need to be trusted such that it is possible to travel between each pair of cities.
Sample Input 1 | Sample Output 1 |
---|---|
2 3 3 1 2 2 3 1 3 5 4 2 1 2 3 4 3 4 5 |
2 4 |