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.