Un arbre (graphe connexe sans cycle) de $N$ sommets vous est donné. Les sommets sont numérotés de $1$ à $N$, et les arêtes de $1$ à $N-1$. Initialement, tous les sommets sont de couleur noire.

Écrivez un programme qui effectue les deux types de requêtes suivants :

• 1 i : change la couleur du sommet $i$ (blanc $\to$ noir, noir $\to$ blanc).
• 2 v : affiche la distance minimale entre le sommet $v$ et tout sommet blanc $u$. Ici, $u$ et $v$ peuvent être identiques. Si $v$ est blanc, la réponse est $0$. S'il n'y a aucun sommet blanc dans l'arbre, affichez $-1$.

Entrée

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

Les $N-1$ lignes suivantes contiennent chacune 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 les requêtes, une par ligne.

Sortie

Pour chaque requête de type $2$, affichez le résultat sur une ligne, dans l'ordre.

Exemples

Entrée

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

Sortie

2
2
2
3
0