Ladder Takahashi

题目描述

有一栋 $10^9$ 层的建筑，有 $N$ 个梯子。
Takahashi 位于第 $1$ 层（最低层），想要通过使用梯子（也可以不使用）到达尽可能高的楼层。
这些梯子编号为 $1$ 到 $N$，梯子 $i$ 连接第 $A_i$ 层和第 $B_i$ 层。可以双向使用梯子 $i$ 从第 $A_i$ 层移动到第 $B_i$ 层或反向移动，但不能在其他楼层之间移动。
Takahashi 可以在同一楼层内自由移动，但不能在没有使用梯子的情况下在楼层之间移动。
Takahashi 能到达的最高楼层是多少？

输入格式

输入按照下列格式从标准输入给出： $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\ldots$ $A_N$ $B_N$

输出格式

输出一个整数，表示答案。

4
1 4
4 3
4 10
8 3

10

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

12

3
500000000 600000000
600000000 700000000
700000000 800000000

1

提示

$1 \leq N \leq 2 \times 10^5$ $1 \leq A_i, B_i \leq 10^9$ $A_i \neq B_i$ 输入中的所有数值均为整数。他可以先使用梯子 $1$ 到达第 $4$ 层，然后使用梯子 $3$ 到达第 $10$ 层，从而到达第 $10$ 层。
他可能无法在楼层之间移动。

标签: AtCoder|abc277C

来源

AtCoder|abc277C