Jaskinia
Limit pamięci: 16 MB
W Bajtocji znajduje się pewna jaskinia.
Jaskinia ta składa się z komór oraz z łączących je korytarzy.
Korytarze są tak ułożone, że między każdymi dwiema komorami można
przejść tylko w jeden sposób.
W jednej z komór Jaś ukrył skarb, ale nie chce powiedzieć w której.
Małgosia koniecznie chce się tego dowiedzieć.
Pyta więc Jasia kolejno o różne komory.
Jeśli Małgosia trafi, to Jaś mówi jej o tym, a jeśli nie trafi,
to mówi jej, w którą stronę trzeba iść z danej komory w kierunku skarbu.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia opis jaskini,
-
obliczy minimalną liczbę pytań, które w pesymistycznym przypadku
musi zadać Małgosia, żeby wiedzieć, w której komorze znajduje się
skarb,
-
wypisze obliczony wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna
dodatnia liczba całkowita , .
Jest to liczba komór w jaskini.
Komory jaskini są ponumerowane od do .
W kolejnych wierszach opisane są korytarze łączące komory,
po jednym w wierszu.
W każdym z tych wierszy znajduje się para różnych dodatnich liczb
całkowitych i (), oddzielonych pojedynczym odstępem.
Para taka oznacza, że komory i są połączone korytarzem.
Wyjście
Na standardowe wyjście powinna być wypisana jedna liczba całkowita,
minimalna liczba pytań, jakie musi zadać Małgosia w pesymistycznym
przypadku (tzn. zakładamy, że Małgosia zadaje pytania najlepiej
jak można, ale skarb jest umieszczony w komorze, która wymaga zadania
największej liczby pytań).
Przykład
Dla danych wejściowych:
5
1 2
2 3
4 3
5 3
poprawną odpowiedzią jest:
2
Autor zadania: Paweł Parys.