W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
Napisz program, który:
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.
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ń).
Dla danych wejściowych:
5 1 2 2 3 4 3 5 3
poprawną odpowiedzią jest:
2
Autor zadania: Paweł Parys.