${10}^9$ қабаттан тұратын ғимаратта $N$ саты бар.

Kalashnikov ең төменгі қабатта ($1$-ші қабатта) тұр және сатыларды пайдалану арқылы ең биік қабатқа жеткісі келеді (қажет болса, ешқандай саты қолданбауға да болады).

Сатылар $1$-ден $N$-ге дейін нөмірленген, және $i$-ші саты $A_i$-ші қабатты $B_i$-ші қабатпен қосады. Сатыны екі бағытта да пайдалануға болады: $A_i$ қабатынан $B_i$ қабатына немесе керісінше, бірақ басқа қабаттарға өтуді қамтамасыз етпейді.

Kalashnikov бір қабаттың ішінде еркін қозғала алады, бірақ қабаттар арасында тек сатыларды пайдаланып қозғала алады.

Kalashnikov жетуі мүмкін ең биік қабат қандай?

Енгізу

Кіріс келесі форматта беріледі:

• Бірінші жолда $N$ бүтін саны.

• Келесі $N$ жолда екі бүтін сан $A_i$ және $B_i$ беріледі.

• $1\le N\le 2\times {10}^5$

• $1\le A_i,B_i\le {10}^9$

• $A_i\ne B_i$

• Кіріс деректерінің барлық мәндері бүтін сандар.

Шығару

Жауап ретінде бір бүтін санды басып шығарыңыз — Kalashnikov жете алатын ең биік қабаты.

Бағалау жүйесі

• Барлығы 25 тест бар, олардың әрқайсысы 4 ұпайдан тұрады.

• мысалдар бағаланбайды.

Мысалдар

Енгізу 1

4
1 4
4 3
4 10
8 3

Жауап 1

10

Енгізу 2

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

Жауап 2

12