配点 : $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$

出力

答えを出力せよ。

4
1 4
4 3
4 10
8 3

10

はしご $1$ で $4$ 階に進み、はしご $3$ で $10$ 階に進むことにより、$10$ 階にたどり着くことができます。

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

12

3
500000000 600000000
600000000 700000000
700000000 800000000

1

他の階への移動ができない場合もあります。