← 返回题目列表

Codeforces · 1704/C

C. 病毒

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

一个圆圈上有 $$$n$$$ 栋房屋,编号从 $$$1$$$ 到 $$$n$$$。对于每个 $$$1 \leq i \leq n - 1$$$,房子 $$$i$$$ 和房子 $$$i + 1$$$ 是邻居;此外,房子$$$n$$$ 和房子$$$1$$$ 也是邻居。

最初,这些 $$$n$$$ 房屋中的 $$$m$$$ 被致命病毒感染。每天早上,琪露诺都可以选择一所没有被感染的房屋,并永久保护该房屋不被感染。

每天,以下事情按顺序发生:

- 琪露诺选择一所未受感染的房屋,并永久保护它。
- 所有至少有一名受感染邻居的未受感染、不受保护的房屋都会受到感染。

琪露诺想要阻止病毒传播。如果她最优地选择要保护的房屋,求最终会被感染的最少房屋数量。

请注意,琪露诺每天都会在病毒传播之前选择要保护的房子。此外,受保护的房屋不会永远受到感染。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行由两个正整数 $$$n, m$$$ ($$$5 \leq n \leq 10^9$$$, $$$1 \leq m \leq \min(n, 10^5)$$$) — 圆圈上的房屋数量以及最初被感染的房屋数量组成。

每个测试用例的第二行由 $$$m$$$ 不同的正整数 $$$a_1, a_2, \cdots , a_m$$$ ($$$1 \leq a_i \leq n$$$) 组成 - 最初感染的房屋的索引。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,单独一行输出一个整数,即最终受感染房屋的最小数量。

示例

输入 #1

8
10 3
3 6 8
6 2
2 5
20 3
3 7 12
41 5
1 11 21 31 41
10 5
2 4 6 8 10
5 5
3 2 5 4 1
1000000000 1
1
1000000000 4
1 1000000000 10 16

输出 #1

7
5
11
28
9
5
2
15

注意

在第一个测试用例中:

第一天开始时,房子 $$$3$$$、$$$6$$$、$$$8$$$ 被感染。选择要保护的房子 $$$2$$$。

第二天开始时,房屋 $$$3$$$、$$$4$$$、$$$5$$$、$$$6$$$、$$$7$$$、$$$8$$$、$$$9$$$ 被感染。选择房屋 $$$10$$$ 进行保护。

第三天开始时,不再有房屋被感染。

在第二个测试用例中:

第一天开始时,房子 $$$2$$$、$$$5$$$ 被感染。选择要保护的房子$$$1$$$。

第二天开始时,房子 $$$2$$$、$$$3$$$、$$$4$$$、$$$5$$$、$$$6$$$ 被感染。没有更多的可用房屋可以得到保护。