← 返回题目列表

Codeforces · 1996/G

G. 佩纳科尼

中文机器翻译题面 查看原题

在梦想之地佩纳科尼,存在 $$$n$$$ 房屋和 $$$n$$$ 道路。对于所有 $$$1 \leq i \leq n-1$$$,在房屋 $$$i$$$ 和 $$$i+1$$$ 之间存在一条道路,并且在房屋 $$$n$$$ 和房屋 $$$1$$$ 之间存在一条道路。所有道路都是双向的。然而,由于佩纳科尼的危机,监管家族负债累累,可能无法维护所有道路。

佩纳科尼居民之间有 $$$m$$$ 的友谊。如果住在 $$$a$$$ 房屋的居民是住在 $$$b$$$ 房屋的居民的朋友,则房屋 $$$a$$$ 和 $$$b$$$ 房屋之间必须有一条经过维护的道路的路径。

必须维护的道路最少数量是多少?

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) – 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5$$$) – 房屋数量和友谊数量。

接下来的 $$$m$$$ 行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a < b \leq n$$$) – 房子 $$$a$$$ 中的居民是房子 $$$b$$$ 中居民的朋友。保证所有 ($$$a, b$$$) 都是不同的。

保证所有测试用例的 $$$n$$$ 和 $$$m$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数,即必须维护的最小道路数量。

示例

输入 #1

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

输出 #1

4
7
2
7
2
3
3

注意

对于第一个测试用例,必须维护以下道路:

- $$$8 \左箭头 \右箭头 1$$$
- $$$7 \左箭头 \右箭头 8$$$
- $$$1 \左箭头 \右箭头 2$$$
- $$$4 \左箭头 \右箭头 5$$$