Kəpənəyin Arxasınca Qaçış

Aydın yay günlərində Nyusha açıq havada kəpənək tutmağı sevir. Amma bu gün ona xüsusilə hiyləgər bir kəpənək rast gəldi: o, labirintə uçdu və orada Nyushanı aldatmağa çalışdı.

Labirint $n$ otaqdan ibarətdir, hansı ki, $1$-dən $n$-ə qədər nömrələnmişdir, və bəzi otaqlar dəhlizlərlə birləşdirilmişdir. Məlumdur ki, hər hansı iki otaq arasında yalnız bir yol var ki, yalnız dəhlizlərdən keçir. Başqa sözlə desək, labirint $n$ zirvə və n - 1 qırağa malik bir ağacdır.

Labirintin giriş qapısı $1$ nömrəli otaqdadır. Yarpaq adlanır ki, hansı ki, yalnız bir başqa otaqla birləşmiş və köklə (1 nömrəli otaqla) üst-üstə düşməyən otaqdır. Hər yarpaqda labirintdən çıxış yerləşir. Kəpənək çıxışlardan birinə doğru $1$ nömrəli otaqdan uçuşa başlayır. O, sabit bir sürətlə hərəkət edir, dönmür və hər dəqiqə bir dəhlizi keçirərək qonşu otağa keçər. Bütün dəhlizlər eyni uzunluğa malikdir.

Nyusha kəpənəyi tutmaq üçün bir neçə dostunu köməyə çağırmağa qərar verdi. Başlanğıcda hər biri çıxış olan hər hansı bir otağa yerləşə bilər. Kəpənək girişdən hər hansı bir çıxışa hərəkətə başladığı zaman, dostlar dərhal öz otaqlarından girişi istiqamətində hərəkətə başlaya bilərlər. Onlar da kəpənəyin sürəti ilə hərəkət edirlər. Əgər onlardan biri kəpənəklə otaqda və ya dəhlizin ortasında qarşılaşsa — o, tutulmuş hesab olunur. Əgər kəpənək heç bir dostla qarşılaşmadan çıxışa çatsa, o uğurla azad olacaq.

Nyusha'ya kəpənəyi mütləq tutmaq üçün lazım olan minimum dost sayını təyin etməkdə kömək edin, kəpənəyin hansı çıxışa uçmasından asılı olmayaraq.