Network Test

What connects us all? Well, it must be the Internet nowadays. With access to the Internet, we can play games, watch drama series, chat with friends, shop online, and order takeout conveniently. Who can ever imagine life without the Internet?

A network is composed of hosts and data links. The hosts refer to terminal devices such as personal computers, mobile phones, and servers, as well as other network devices including switches and routers. A data link is a direct connection between two hosts, over which the data packets can be transmitted in either direction. Data links can be implemented in various physical forms; the most common ones are copper cables, optical fibers, and radio waves, to name but a few.

Since it is generally not practical to build data links between every pair of hosts, the data packets may pass through intermediate hosts when the source host and the destination host are not adjacent. There are many possible routes between two hosts, so we need a routing protocol to decide which route to use. The simplest routing protocol is the Spanning Tree Protocol (STP). In STP, only a subset of all data links are enabled such that every two hosts are reachable and there is no cycle in the enabled data links. The set of enabled data links is called a spanning tree, and it is clear that there is a unique path composed of only enabled data links between any two hosts.

The Network Construction Company have just set up a network, and they want to test whether all data links work properly. To do this, they plan to carry out several rounds of testing. In each round of testing, a spanning tree is chosen and the packages are transmitted via only the data links in the spanning tree, so that the connectivity of every enabled data link can be tested. They want to minimize the number of testing rounds conducted, under the premise that every data link in the network is tested in at least one round.

The first line of the input consists of only a single integer $T$ $(1 \leq T \leq 50)$, indicating the number of test cases.

Each test case begins with two integers $n, m$ $(2 \leq n \leq 1000, 1 \leq m \leq 2000)$, where $n$ is the number of hosts and $m$ is the number of data links. Then follow $m$ lines, each containing two integers $u, v$ $(1 \leq u, v \leq n, u \neq v)$, denoting a data link between two hosts numbered $u$ and $v$. There may be more than one data link between a pair of hosts. It is guaranteed that every two hosts are reachable via the given data links.

There are no more than 20 test cases with $m > 500$.

For each test case, print the minimum number of rounds conducted as an integer in a single line.

2
3 3
1 2
2 3
3 1
4 7
1 3
1 2
1 4
3 2
3 4
2 4
4 2

2
3

2020 Multi-University Training Contest 10