/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
10^9 階建てのビルがあり、N 本のはしごがかかっています。
ビルの 1 階にいる高橋君ははしごを繰り返し使って（0 回でもよい）できるだけ高い階へ上りたいと考えています。
はしごには 1 から N までの番号がついており、はしご i は A_i 階と B_i 階を結んでいます。はしご i を利用すると A_i 階から B_i 階へ、または B_i 階から A_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 階に進むことにより、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
他の階への移動ができない場合もあります。
Score : 300 points
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.