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 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:
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.
Napisz program, który:
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.
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.
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.