551. 抢票

你正在出售电影院前排座位的门票。

前排共有 $N$ 个座位,从左到右编号为 $1$ 到 $N$。

短短一个周末的时间,就堆积了关于座位的 $Q$ 个预订请求!

第 $i$ 个预订要求订下从编号 $L_i$ 到 $R_i$ 的所有座位。

你现在将每个预订输入系统,一次输入一个。

由于某些预订可能会重叠,因此系统可能无法完全满足每个预订。

当你在系统中输入一个预订时,系统会将该预订所请求的座位里所有还未进行分配的座位分配给该预订。

现在要求每个订单都至少分配 $k$ 个座位,请问 $k$ 最大是多少。

输入格式

第一行包含整数 $T$,表示共有 $T$ 组测试数据。

每组测试数据第一行包含两个整数 $N$ 和 $Q$。

接下来 $Q$ 行,每行包含两个整数 $L_i$ 和 $R_i$。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为 Case #x: y,其中 $x$ 为组别编号(从 $1$ 开始),$y$ 为 $k$ 的最大值。

数据范围

$1 \le T \le 100$,
$1 \le N \le 10^6$,
$1 \le L_i \le R_i \le N$,
$1 \le Q \le 30000$

输入样例:

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$。