codeforces#P1996G. Penacony

Penacony

Description

On Penacony, The Land of the Dreams, there exists $n$ houses and $n$ roads. There exists a road between house $i$ and $i+1$ for all $1 \leq i \leq n-1$ and a road between house $n$ and house $1$. All roads are bidirectional. However, due to the crisis on Penacony, the overseeing family has gone into debt and may not be able to maintain all roads.

There are $m$ pairs of friendships between the residents of Penacony. If the resident living in house $a$ is friends with the resident living in house $b$, there must be a path between houses $a$ and $b$ through maintained roads.

What is the minimum number of roads that must be maintained?

The first line contains $t$ ($1 \leq t \leq 10^4$) – the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($3 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5$) – the number of houses and the number of friendships.

The next $m$ lines contain two integers $a$ and $b$ ($1 \leq a < b \leq n$) – the resident in house $a$ is friends with the resident in house $b$. It is guaranteed all ($a, b$) are distinct.

It is guaranteed the sum of $n$ and $m$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, output an integer, the minimum number of roads that must be maintained.

Input

The first line contains $t$ ($1 \leq t \leq 10^4$) – the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($3 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5$) – the number of houses and the number of friendships.

The next $m$ lines contain two integers $a$ and $b$ ($1 \leq a < b \leq n$) – the resident in house $a$ is friends with the resident in house $b$. It is guaranteed all ($a, b$) are distinct.

It is guaranteed the sum of $n$ and $m$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output an integer, the minimum number of roads that must be maintained.

7
8 3
1 8
2 7
4 5
13 4
1 13
2 12
3 11
4 10
10 2
2 3
3 4
10 4
3 8
5 10
2 10
4 10
4 1
1 3
5 2
3 5
1 4
5 2
2 5
1 3
4
7
2
7
2
3
3

Note

For the first test case, the following roads must be maintained:

  • $8 \leftarrow \rightarrow 1$
  • $7 \leftarrow \rightarrow 8$
  • $1 \leftarrow \rightarrow 2$
  • $4 \leftarrow \rightarrow 5$