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。