$N$ sommets formant un arbre (graphe connexe sans cycle non orienté). Les sommets sont numérotés de $1$ à $N$, et les arêtes sont numérotées de $1$ à $N-1$. Initialement, tous les sommets sont blancs.

Écrivez un programme qui exécute les deux requêtes suivantes :

• 1 i : Change la couleur du sommet $i$ (blanc → noir, noir → blanc).
• 2 v : Affiche le numéro du premier sommet noir sur le chemin du sommet $1$ au sommet $v$. S’il n’y a pas un tel sommet, affichez $-1$.

Entrée

La première ligne contient $N$ ($2 \le N \le 100\,000$).

Les $N-1$ lignes suivantes contiennent deux entiers $u$ et $v$, les sommets reliés par l’arête $i$.

La ligne suivante contient le nombre de requêtes $M$ ($1 \le M \le 100\,000$).

Les $M$ lignes suivantes contiennent chacune une requête.

Sortie

Pour chaque requête de type 2, affichez le résultat sur une ligne séparée, dans l’ordre.

Exemples

Entrée 1

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

Sortie 1

-1
8
-1
2
-1