TR-H4. Navbatchi o‘qituvchilar

Litseyda n ta xona n − 1 ta yo‘lak bilan daraxt shaklida ulangan. Tanaffusda ba’zi xonalarga navbatchi o‘qituvchi qo‘yiladi. Navbatchi o‘z xonasini va yo‘lak bilan bevosita ulangan qo‘shni xonalarni kuzatadi.

Har bir xona kuzatilishi uchun eng kamida nechta navbatchi kerak?

Kirish ma’lumotlari

Birinchi qatorda n. Keyingi n − 1 qatorda yo‘laklar u v.

Chiqish ma’lumotlari

Bitta son — navbatchilarning eng kam soni.

Cheklovlar

1 ≤ n ≤ 2·10⁵.

1-misol (zanjir 1–2–3–4–5): 2- va 4-xonaga navbatchi — 2 kishi. Bitta navbatchi ko‘pi bilan 3 xonani ko‘radi.