← 返回题目列表

Codeforces · 1297/B

B. 卡通

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

Tanya 喜欢卡通。她知道 $$$n$$$ 新动画片将在他最喜欢的电影院上映:其中 $$$i$$$ 将从 $$$a_i$$$ 日到 $$$b_i$$$ 日播出 ($$$1 \le a_i \le b_i \le 10^9$$$)。

电影院有优惠:每天只播放一部动画片,就有很大的折扣。

Tanya 不在乎她会看哪部动画片,但她想省一些钱。这就是为什么她要求您找到只有一部动画片播出的任何一天 $$$x$$$。形式上:找到 $$$x$$$,使得恰好存在一个 $$$i$$$ ($$$1 \le i \le n$$$) 和 $$$a_i \le x \le b_i$$$。如果有多个可能的答案,请打印其中任何一个。如果没有这一天,则打印-1。

输入

第一行包含单个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。以下是 $$$t$$$ 测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$) — 卡通片的数量。

在接下来的 $$$n$$$ 行中,每行一个卡通片本身由一对整数 $$$a_i$$$、$$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$) 描述 - 第 $$$i$$$ 卡通片的第一个和最后一个播出日。

保证输入中所有测试用例的值 $$$n$$$ 的总和不超过 $$$2000$$$。

输出

按照给定测试用例在输入中出现的顺序打印 $$$t$$$ 答案:第 $$$i$$$ 个答案是这样的 $$$x$$$,即只有一部动画片会在 $$$x$$$ 日播出,如果没有这样的日子,则为 -1。

示例

输入 #1

5
1
1 1
3
2 1000000000
2 500000000
500000002 1000000000
3
1 2
3 4
1 4
2
4 11
4 9
3
1 5
10 10
1 5

输出 #1

1
500000001
-1
10
10

注意

在第三个测试用例中:在$$$1$$$和$$$2$$$天,将播放第一部和第三部动画片,在$$$3$$$和$$$4$$$天,将播放第二部和第三部动画片。所以,没有一天只播放一部动画片。

在第四个测试用例中,$$$11$$$ 也是一个可能的答案。