Score : $300$ points

问题描述

存在一座高度为 $10^9$ 层的大楼，其中共有 $N$ 条梯子。
Takahashi 正位于第 $1$ 层（最低层），他希望通过使用梯子（可能不使用任何梯子）到达尽可能高的楼层。
这些梯子从 $1$ 到 $N$ 编号，其中第 $i$ 条梯子连接着第 $A_i$ 层和第 $B_i$ 层。可以双向使用第 $i$ 条梯子，在第 $A_i$ 层与第 $B_i$ 层之间移动，但不能在其他楼层之间直接移动。
Takahashi 可以在同一楼层内自由移动，但在不借助梯子的情况下无法在不同楼层之间移动。
请问 Takahashi 最多能到达哪一层楼？

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 11:39:21