Zadanie
Limit pamięci: 128 MB
Bajtazar przygotowuje właśnie zadanie na konkurs programistyczny. Napisał już szkic treści:
W Bajtocji jest miast połączonych dwukierunkowymi drogami w taki sposób, że korzystając z sieci drogowej da się przejechać pomiędzy dowolnymi dwoma miastami.
Przebycie drogi łączącej dwa bezpośrednio połączone miasta zajmuje jedną godzinę.
Miasta są ponumerowane od do .
W mieście mieszka mieszkańców.
W przyszłym roku w Bajtocji mają się odbyć wybory.
Aby mieć pełną kontrolę nad przebiegiem głosowania, król Bajtocji postanowił, że głosowanie zostanie zorganizowane w tylko jednym mieście.
Wszyscy mieszkańcy Bajtocji udadzą się najkrótszą drogą do miasta z urną wyborczą i tam oddadzą głos.
Teraz pozostało wybrać miasto, w którym odbędzie się głosowanie.
Wybór ten zależy od wielu czynników.
W szczególności, dla każdego miasta chcielibyśmy obliczyć łączny czas potrzebny wszystkim mieszkańcom Bajtocji na dotarcie do miasta (oznaczmy tę wartość przez ) [...]
Bajtazar miał już przygotowane wyjątkowo trudne testy do zadania, jednak przypadkiem stracił połowę danych.
Teraz z każdego testu pozostały mu tylko opisy połączeń drogowych i pliki wyjściowe zawierające wartości .
Na tej podstawie chciałby odtworzyć liczbę mieszkańców każdego miasta Bajtocji.
Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita () oznaczająca liczbę miast w Bajtocji.
Każdy z kolejnych wierszy zawiera opis jednego połączenia drogowego w postaci pary liczb całkowitych , ().
Oznaczają one, że miasta oraz są połączone drogą.
Kolejny wiersz zawiera ciąg liczb całkowitych ().
Wyjście
Wypisz jeden wiersz z ciągiem liczb całkowitych .
Liczba powinna oznaczać liczbę mieszkańców miasta Bajtocji numer .
Dla podanego ciągu , po rozwiązaniu zadania Bajtazara powinno się otrzymać ciąg podany na wejściu.
Dane wejściowe są tak dobrane, że odpowiedź zawsze istnieje. Jeśli istnieje
wiele poprawnych odpowiedzi, Twój program może wypisać dowolną z nich.
Przykład
Dla danych wejściowych:
2
1 2
17 31
poprawną odpowiedzią jest:
31 17
Autor zadania: Jakub Pachocki.