Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0040 - FLYING SAFELY

   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 be- tween 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 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 n 1 000) and m (1 m 10 000): the number of cities and the number of pilots, respectively.
  • m lines with two space-separated integers a and b (1 a, b n, a ƒ= 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 and integer: the minimum number of pilots that need to be trusted such that it is possible to travel between each pair of cities.

Examples

stdin

stdout

1

2

3 3

1 2

2 3

1 3

5 4

2 1

2 3

4 3

4 5

2

4


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2013-12-24
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.ADA95 DOC ASM64 BASH BF C CSHARP C++ 4.3.2 CPP C99 LISP sbcl LISP clisp GO JAVA JS-RHINO LUA NICE NODEJS OCAML PAS-GPC PAS-FPC PERL PERL6 PHP PRLG-swi PYTHON PYTHON3 RUBY SCALA SCM qobi ST
Աղբյուրը.Benelux (BAPC) 2013.F

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.