Dane jest drzewo (spójny graf nieskierowany bez cykli) składające się z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$, a krawędzie od $1$ do $N-1$. Początkowo wszystkie wierzchołki są białe.

Napisz program wykonujący następujące dwa zapytania:

• 1 i: zmienia kolor wierzchołka $i$ (biały -> czarny, czarny -> biały)
• 2 v: wypisuje numer pierwszego czarnego wierzchołka na ścieżce z wierzchołka $1$ do wierzchołka $v$. Jeżeli taki wierzchołek nie istnieje, wypisz $-1$.

Wejście

Pierwszy wiersz zawiera $N$ ($2 \le N \le 100\,000$).

W kolejnych $N-1$ wierszach znajdują się pary liczb $u$ i $v$ oznaczające krawędź $i$.

Następny wiersz zawiera $M$ ($1 \le M \le 100\,000$) – liczbę zapytań.

W kolejnych $M$ wierszach znajdują się zapytania, każde w osobnym wierszu.

Wyjście

Dla każdego zapytania typu $2$ wypisz wynik w osobnej linii, w kolejności wystąpienia.

Przykład

Wejście

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

Wyjście

-1
8
-1
2
-1