TR-E2. Eng uzoq ikki xona

Litsey binosida n ta xona n − 1 ta eshik bilan shunday ulanganki, istalgan ikki xona orasida yagona yo‘l bor. Bir eshikdan o‘tish — bir qadam.

Bir-biridan eng uzoq joylashgan ikki xona orasida necha qadam bor?

Kirish ma’lumotlari

Birinchi qatorda n. Keyingi n − 1 qatorda eshik bilan ulangan xonalar u v.

Chiqish ma’lumotlari

Bitta son — eng uzoq ikki xona orasidagi qadamlar soni.

Cheklovlar

1 ≤ n ≤ 2·10⁵; eshiklar daraxt hosil qiladi.

1-misol: 4-xonadan 6-xonagacha 4 → 2 → 1 → 3 → 5 → 6 — 5 qadam.