Stacja

Limit pamięci: 192 MB

W Bajtocji zakończył się pierwszy etap reformy (Został on opisany w zadaniu Koleje z III etapu XIV OI. Znajomość zadania Koleje nie jest jednak w najmniejszym stopniu potrzebna do rozwiązania niniejszego zadania.) sieci kolejowej. Owa sieć składa się z dwukierunkowych odcinków torów łączących stacje kolejowe. Żadne dwie stacje nie są połączone więcej niż jednym odcinkiem torów. Ponadto wiadomo, że z każdej stacji kolejowej da się dojechać do każdej innej dokładnie jedną trasą. Trasa może być złożona z kilku odcinków torów, ale nigdy nie przechodzi przez żadną stację więcej niż raz.

Celem drugiego etapu reformy jest zaplanowanie połączeń kolejowych. Bajtazar liczy na to, że mu w tym pomożesz. Aby uprościć zadanie, Bajtazar postanowił, że:

• jedna ze stacji stanie się wielkim węzłem kolejowym i otrzyma nazwę Bitowice,
• ze wszystkich pozostałych stacji uruchomione zostaną połączenia kolejowe do Bitowic i z powrotem,
• każdy pociąg będzie jeździł między Bitowicami i drugą stacją końcową po jedynej możliwej trasie, zatrzymując się na wszystkich mijanych stacjach.

Pozostaje pytanie o to, która stacja powinna zostać Bitowicami. Postanowiono, że system połączeń powinien być tak zaplanowany, by średni koszt przejazdu między dwiema różnymi stacjami kolejowymi był minimalny. W Bajtocji obowiązują wyłącznie bilety jednorazowe w cenie 1 bajtalara, upoważniające do przejazdu jednym połączeniem na dowolną odległość. Tak więc koszt przejazdu między dwiema konkretnymi stacjami to minimalna liczba połączeń, jakie trzeba wykorzystać, aby przejechać z jednej stacji do drugiej.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis sieci kolejowej w Bajtocji,
• wyznaczy stację, która powinna zostać Bitowicami,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia zapisana jest jedna liczba całkowita () - jest to liczba stacji kolejowych. Stacje kolejowe są ponumerowane od do . Stacje łączy odcinków torów kolejowych. Są one opisane w kolejnych wierszach, po jednym w wierszu. W każdym z nich są zapisane dwie dodatnie liczby całkowite oraz (), oddzielone pojedynczym odstępem i oznaczające numery stacji, które łączy dany odcinek torów.

Wyjście

W pierwszym i jedynym wierszu wyjścia Twój program powinien wypisać jedną liczbę całkowitą - optymalną lokalizację stacji Bitowice. Jeżeli istnieje więcej niż jedna optymalna odpowiedź, Twój program powinien wypisać dowolną z nich.

Przykład

Dla danych wejściowych:

8
1 4
5 6
4 5
6 7
6 8
2 4
3 4

poprawną odpowiedzią jest:

7

Kółka na rysunku reprezentują stacje (liczby w kółkach to numery stacji), a krawędzie to odcinki torów. Możliwymi optymalnymi lokalizacjami Bitowic są stacje 7 oraz 8. W przypadku wyboru dowolnej z nich, średni koszt przejazdu między różnymi stacjami będzie równy (w przykładzie jest par nieuporządkowanych różnych stacji).

Autor zadania: Marcin Kubica.