Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_30_05 - Podróż do stolicy

Sieć kolejowa w Bajtocji spełnia prostą zasadę: z dowolnego miasta można dostać się do każdego z pozostałych miast tylko jednym sposobem. 

Bajtek i Bitek to dwaj starzy przyjaciele, którzy postanowili wspólnie wybrać się pociągiem na wycieczkę do Bajtogrodu - stolicy kraju. Ponieważ nie chcą tracić czasu i pieniędzy na niepotrzebną jazdę, przyjaciele umówili się tak, że każdy wyjedzie ze swojego miasta w kierunku stolicy i spotkają się w najbliższym mieście, które leży na trasie każdego z nich (takim miastem może być dopiero Bajtogród). Dalej pojadą już razem i pewnie miło spędzą czas na wspominaniu dawnych czasów.

Przyjaciół interesuje to, w którym mieście się spotkają.

Wejście

W pierwszej linii liczba miast n (1 ≤ n ≤ 200000).

W każdej z kolejnych n−1 linii dwie liczby oznaczające numery miast połączonych bezpośrednio linią kolejową. Miasta numerowane są od 1 do n, a stolica ma numer 1.

Następnie liczba zapytań q (1q200000).

W kolejnych q lniach po dwie liczby całkowite oznaczające numery miast, w których mieszkają przyjaciele.

Wyjście

Dla każdego zapytania, w oddzielnej linii numer miasta, w którym spotkają się przyjaciele na drodze do stolicy.

Przykład

Wejście:
5
1 2
2 3
5 2
4 1
3
3 5
5 4
3 3
Wyjście:
2
1
3

Dodane przez:Witold Długosz
Data dodania:2016-10-24
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie: ALGOLIGA 30

ukryj komentarze
2016-10-30 22:22:57 Witold D³ugosz
Dzięki narbej za spostrzegawczość.
2016-10-30 20:54:23 narbej
W pierwszej linii liczba [testów] miast
może zamiast: " w których mieszkają przyjaciele." trochę lepiej: w których aktualnie przebywają przyjaciele" ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.