Il y a un arbre (graphe connexe sans cycle non orienté) constitué de $N$ sommets. 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 de couleur noire.

Écrivez un programme qui effectue les deux requêtes suivantes :

• 1 i : change la couleur du sommet $i$ (blanc $\to$ noir, noir $\to$ blanc).
• 2 u : compte le nombre de sommets $v$ connectés à $u$. Deux sommets sont dits connectés si tous les sommets sur le chemin qui les relie sont de la même couleur.

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 connecté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, dans l'ordre des requêtes.

Exemples

Entrée 1

5
1 2
1 3
1 4
1 5
3
2 1
1 1
2 1

Sortie 1

5
1

Entrée 2

7
1 2
1 3
2 4
2 5
3 6
3 7
4
2 1
1 1
2 2
2 3

Sortie 2

7
3
3