Due to budget cuts, even spies have to use commercial
airlines nowadays to travel between cities in the world.
Although this mode of travel can be very convenient for a spy,
it also raises a problem: the spy has to trust the pilot to
make sure he is not in danger during the flight. And even
worse, sometimes there is no direct flight between some pairs
of cities, so that the spy has to take multiple flights to get
to the desired location, and thus has to trust multiple pilots!
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
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
Per test case:
|Sample Input 1
||Sample Output 1