在梦想之地佩纳科尼,存在 $$$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$$$