Problem D
Reachable Roads

After the major earthquake and fires to your town, planners are assessing the damages to the roads in the city. Some roads are just gone, and others are impassable. The result is that it is impossible to get from some places to others. The planners want to get the city running quickly. Therefore they want to add as few roads as possible to get a city where everyone can reach everyone else.

We’ll make the simplifying assumptions that building any road is the same cost as building any other road, and that all roads are bidirectional.

The planners have asked you to find the minimum number of roads that they can add to the current grid so that everyone can get everywhere.

Input

Input starts with a line containing an integer $1 \le n \le 100$ indicating the number of cities that follow. Each city’s description starts with a line describing the number of road endpoints $1 \le m \le 1\, 000$. Each endpoint is in the range $0$ to $m-1$. This is followed by a number $0 \le r \le \min (m(m-1)/2, 10m)$, then a list of $r$ pairs of endpoints which are directly connected by a usable road. Each pair appears on its own line, all pairs are distinct, and all roads connect to different endpoints.

Output

For each city description, output the minimum number of roads that must be added.

2
5
3
0 1
1 2
3 4
2
1
0 1

1
0