CF1996G Penacony

在梦乡 $\text{Penacony}$ ，有 $n$ 栋房子和 $n$ 条双向的路。第 $i$ 栋和第 $i+1$ 栋房子（包括第 $n$ 和第 $1$ 栋之间）有双向的路连接。然而，由于梦乡的危机，领主陷入债务，难以维护所有的路。 梦乡的居民之中，有 $m$ 对好朋友。如果住在 $a$ 栋的居民和住在 $b$ 栋的居民是好朋友，那么他们必须能够通过受到维护的道路相互来往，即要求维护 $a$ 栋和 $b$ 栋之间那些的路。 请求出梦乡的领主最少需要维护多少条路。

第一行是 $t$ ，表示测试组数。 接下来每组的第一行是 $n$ 和 $m$，有 $3 \le n \le 2\cdot10^5, 1 \le m \le 2\cdot10^5$，表示房子栋数和好朋友对数。 之后的 $m$ 行每行有两个整数 $a$ 和 $b$ ，有 $1\le a < b\le n$ ，表示 $a$ 栋和 $b$ 栋的居民是好朋友。保证每对 $(a,b)$ 都不同。 同时还保证所有测试组的 $n$ 和 $m$ 之和不超过 $2\cdot10^5$.

每组输出一行，表示最少需要维护的道路数。

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 $