题目描述

你正在销售电影院前排座位的门票。前排有 $N$ 个座位，从左到右编号为 $1$ 到 $N$。你上周不在办公室，回来时发现积压了 $Q$ 个座位预订！第 $i$ 个预订请求从 $L_i$ 到 $R_i$（包含两端）的所有座位。你现在需要将这些预订逐一输入系统，这是一项枯燥的工作。

由于某些预订可能重叠，系统可能无法完全满足每个预订。当你将一个预订输入系统时，系统会分配该预订请求的、且尚未被更早输入的预订所分配的所有座位。

请问，最大的整数 $k$ 是多少，使得存在一种输入预订的顺序，让每个预订都被分配到至少 $k$ 个座位？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $Q$，分别表示座位数量和预订数量。随后有 $Q$ 行，其中第 $i$ 行包含两个整数 $L_i$ 和 $R_i$，表示第 $i$ 个预订希望预订从 $L_i$ 到 $R_i$（包含两端）的所有座位。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是上述最大的 $k$ 值。

3
5 3
1 2
3 4
2 5
30 3
10 11
10 10
11 11
10 4
1 8
4 5
3 6
2 7

Case #1: 1
Case #2: 0
Case #3: 2

提示

在样例 #1 中，有 $N = 5$ 个座位和 $Q = 3$ 个预订。一种可能的顺序是：

• 先输入第二个预订，系统会分配 $2$ 个座位（$3$ 和 $4$）。
• 再输入第一个预订，系统会分配 $2$ 个座位（$1$ 和 $2$）。
• 最后输入第三个预订，系统会分配 $1$ 个座位（仅剩座位 $5$，因为 $1$、$2$、$3$、$4$ 已被预订）。

每个预订都被分配到至少 $1$ 个座位，且不存在一种顺序能让每个预订分配到至少 $2$ 个座位，因此答案为 $1$。

在样例 #2 中，有 $N = 30$ 个座位和 $Q = 3$ 个预订。无论以何种顺序分配座位，至少有一个预订将分不到任何座位，所以答案为 $0$。注意，可能存在不属于任何预订的座位！

在样例 #3 中，有 $N = 10$ 个座位和 $Q = 4$ 个预订。一种可能的顺序是：

• 先输入第二个预订，系统会分配 $2$ 个座位（$4$ 和 $5$）。
• 再输入第三个预订，系统会分配 $2$ 个座位（$3$ 和 $6$，因为 $4$ 和 $5$ 已被预订）。注意，分配到的座位不一定相邻。
• 接着输入第四个预订，系统会分配 $2$ 个座位（$2$ 和 $7$）。
• 最后输入第一个预订，系统会分配 $2$ 个座位（$1$ 和 $8$）。

每个预订都被分配到至少 $2$ 个座位，且不存在一种顺序能让每个预订分配到至少 $3$ 个座位，因此答案为 $2$。

注意：对于本题的大数据集，我们不建议使用解释型/较慢的语言。

限制条件

$T = 100$。

$1 \le N \le 10^6$。

$1 \le L_i \le R_i \le N$。

测试集 1（可见）

$1 \le Q \le 300$。

测试集 2（隐藏）

$1 \le Q \le 30000$。

在至少 $85$ 个测试用例中，$Q \le 3000$。

翻译由 DeepSeek V4 Pro 完成