Wakacyjne Warsztaty Olimpijskie 2021

Wersja łatwa zadania różni się od wersji trudnej wyłącznie rozmiarem danych wejściowych.

Dane jest drzewo o n wierzchołkach ponumerowanych od 1 do n. Wierzchołki połączone są n - 1 nieskierowanymi krawędziami. Korzeniem drzewa jest wierzchołek o numerze 1.

Twoim zadaniem jest znalezienie najniższego wspólnego przodka dla każdej z q par wierzchołków.

Wejście

W pierwszej linii znajduje się liczba wierzchołków n (1 ≤ n ≤ 100). W kolejnych n - 1 liniach znajdują się opisy krawędzi.

Opis każdej krawędzi składa się z dwóch liczb u oraz v (1 ≤ u, v ≤ n u ≠ v) określających numery połączonych wierzchołków.

W następnej linii znajduje się liczba zapytań q (1 ≤ q ≤ 4950). W kolejnych q liniach znajdują się zapytania.

Każde zapytanie składa się z dwóch liczb u oraz v (1 ≤ u, v ≤ n u ≠ v) określających numery wierzchołków, dla których należy znaleźć najniższego wspólnego przodka.

Wyjście

Dla każdego zapytania należy w osobnej linii wypisać numer wierzchołka będącego najmniejszym wspólnym przodkiem podanej pary wierzchołków.

Przykład

Wejście:

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

Wyjście:

1
2
1
5
1