← 返回题目列表

Codeforces · 1834/D

D. 课堂调查

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

Zinaida Viktorovna 的历史课上有 $$$n$$$ 名学生。今天的作业包括$$$m$$$主题,但学生们准备的时间很少,所以$$$i$$$-th学生只学习了从$$$l_i$$$到$$$r_i$$$的主题。

课程开始时,每个学生都将手握在 $$$0$$$ 处。老师想问一些话题。事情是这样的:

- 老师提出主题$$$k$$$。
- 如果学生已经学习了主题$$$k$$$,那么他将举手$$$1$$$,否则他将手放下$$$1$$$。

每个主题 Zinaida Viktorovna 只能询问一次。

找出调查后班级中可以出现的最高手和最低手的高度的最大差值。

请注意,学生的手牌可能会低于 $$$0$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 10^5, 1 \le m \le 10^9$$$) – 分别是学生数量和主题数量。

每个测试用例接下来的 $$$n$$$ 行都包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$) - 第 $$$i$$$ 个学生已学习的主题段的端点。

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

输出

对于每个测试用例,打印一个整数 - 调查后班级中最高手和最低手的高度的最大差值。

示例

输入 #1

6
4 8
2 6
4 8
2 7
1 5
3 3
1 3
2 3
2 2
3 5
1 5
1 5
1 5
3 5
1 1
3 3
5 5
4 7
1 7
1 3
3 3
4 5
2 4
1 3
2 4

输出 #1

6
4
0
2
12
2

注意

在第一个测试用例中,Zinaida Viktorovna 可以询问主题 $$$5, 6, 7, 8$$$。那么第 $$$2$$$-nd 学生的手将位于 $$$4$$$ 的高度,第 $$$4$$$-th 学生的手将位于 $$$-2$$$ 的高度,也就是说,差值将等于 $$$6$$$。

在第二个测试用例中,您可以询问主题 $$$1$$$ 和 $$$3$$$。那么第 $$$1$$$-st 学生的手将位于 $$$2$$$ 高度,$$$3$$$-rd 学生的手将位于 $$$-2$$$ 高度。所以差额为$$$4$$$。

在第三个测试用例中,对于所询问的任何一组主题,最高手牌和最低手牌之间的差异将为 $$$0$$$。

在第五个测试用例中,您可以询问所有主题。那么$$$1$$$-st 和$$$3$$$-rd 学生的手部高度之间的差异将为$$$12$$$。