102772: [AtCoder]ABC277 C - Ladder Takahashi

Problem Statement

There is a $10^9$-story building with $N$ ladders.
Takahashi, who is on the $1$-st (lowest) floor, wants to reach the highest floor possible by using ladders (possibly none).
The ladders are numbered from $1$ to $N$, and ladder $i$ connects the $A_i$-th and $B_i$-th floors. One can use ladder $i$ in either direction to move from the $A_i$-th floor to the $B_i$-th floor or vice versa, but not between other floors.
Takahashi can freely move within the same floor, but cannot move between floors without using ladders.
What is the highest floor Takahashi can reach?

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq 10^9$
• $A_i \neq B_i$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\ldots$
$A_N$ $B_N$

Output

Print an integer representing the answer.

Sample Input 1

4
1 4
4 3
4 10
8 3

Sample Output 1

10

He can reach the $10$-th floor by using ladder $1$ to get to the $4$-th floor and then ladder $3$ to get to the $10$-th floor.

Sample Input 2

6
1 3
1 5
1 12
3 5
3 12
5 12

Sample Output 2

12

Sample Input 3

3
500000000 600000000
600000000 700000000
700000000 800000000

Sample Output 3

1

He may be unable to move between floors.

问题描述

有一座有$10^9$层的大楼，有$N$个梯子。
在第$1$层（最低层）的高桥，想通过使用梯子（可能不使用）尽可能地到达更高的楼层。
梯子从$1$到$N$编号，梯子$i$连接第$A_i$层和第$B_i$层。一个人可以使用梯子$i$在任意方向上从第$A_i$层移动到第$B_i$层或反之，但不能在其他楼层之间移动。
高桥可以在同一楼层内自由移动，但不能不使用梯子在楼层之间移动。
高桥可以到达的最高楼层是哪一层？

约束

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq 10^9$
• $A_i \neq B_i$
• 输入中的所有值都是整数。

输入

输入从标准输入以以下格式给出：

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\ldots$
$A_N$ $B_N$

输出

打印一个表示答案的整数。

样例输入 1

4
1 4
4 3
4 10
8 3

样例输出 1

10

他可以通过使用梯子$1$到达第$4$层，然后使用梯子$3$到达第$10$层。

样例输入 2

6
1 3
1 5
1 12
3 5
3 12
5 12

样例输出 2

12

样例输入 3

3
500000000 600000000
600000000 700000000
700000000 800000000

样例输出 3

1

他可能无法在楼层之间移动。