Polish version    English version  
  Historia OI -> XI OI 2003/2004 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
XI Olimpiada Informatyczna 2003/2004

Zadanie: jaskinia

Jas

Zawody II stopnia  
Plik źródłowy: jas.xxx (xxx=pas,c,cpp)
Limit pamięci: 16 MB

Alternatywne formaty: PostScript

W Bajtocji znajduje się pewna jaskinia. Jaskinia ta składa się z n 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 n, 1<= n <= 50,000. Jest to liczba komór w jaskini. Komory jaskini są ponumerowane od 1 do n. W kolejnych n-1 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 a i b (1<= a,b <= n), oddzielonych pojedynczym odstępem. Para taka oznacza, że komory a i b 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

prawidłową odpowiedzią jest:

2



Wersja do druku