Electric Network

The Large veHicle Collider (LHC) is the world's largest and highest-energy vehicle accelerator, designed to collide two vehicles at very high kinetic energy. Its goal is to study how vehicle structures behave in a collision, filling a missing link in the vehicle safety model and revealing how the elementary parts of a vehicle interact in an emergency.

The vehicles used in the LHC run on electric motors, and the experiments draw an enormous amount of electric power, so every facility is joined by a network of electric lines. A network is called doubly linked if any two facilities stay connected, directly or indirectly, even when any single electric line fails.

The LHC wants to add as few new electric lines as possible to make its network doubly linked, without installing any redundant line. Given a network in which every facility is already connected through the existing electric lines, compute the minimum number of new electric lines needed to make the network doubly linked.

Figure (a)

Figure (b)

Figure (c)

Figure (a) is a doubly linked network. Figure (b) is not doubly linked, because removing the single line between the two vehicles disconnects the network. Adding one more line, as shown in Figure (c), makes the network doubly linked.

The first line contains the number of test cases $T$ ($1 \le T \le 20$).

Each test case begins with a line containing two integers $N$ and $M$ ($1 \le N \le 1000$, $1 \le M \le 100{,}000$), the number of facilities and the number of electric lines already installed. Each of the next $M$ lines contains two integers $a$ and $b$ ($0 \le a, b \le N-1$), meaning an electric line directly connects facilities $a$ and $b$.

The input never lists the same pair of facilities twice, but installing more than one line between two facilities is allowed when adding new lines.

For each test case, print a single line with the minimum number of electric lines that must be added to make the network doubly linked.