Minimum Road Addition for Province Connectivity

You are given data for M provinces. Each province is described by the number of cities C and a number of existing bidirectional roads R that connect some pairs of cities. Your task is to determine for each province the minimum number of additional roads required to connect all its cities into a single connected network.

For a province, if the graph of cities has k connected components, then the number of roads needed is given by \(k - 1\). For example, if a province has 4 cities and the existing roads connect cities 1 with 2 and cities 3 with 4, then there are 2 connected components, and you need \(2 - 1 = 1\) additional road to interconnect all cities.

Read the input from stdin and output your answer to stdout.

inputFormat

The input begins with an integer M indicating the number of provinces.

For each province, the first line contains two integers C and R, where:

• C is the number of cities in the province.
• R is the number of roads that already exist.

This is followed by R lines, each containing two integers u and v (1 ≤ u, v ≤ C) representing a bidirectional road connecting city u and city v.

All integers are separated by spaces or newline characters.

outputFormat

Output a single line containing M integers, where the i-th integer corresponds to the minimum number of additional roads required to interconnect all cities in the i-th province. The results should be output in the same order as the provinces are given in the input, with each value separated by a space.

## sample

2
4 2
1 2
3 4
3 1
1 2

1 1