Hay un árbol (grafo conexo sin ciclos no dirigidos) de $N$ vértices. Los vértices están numerados del $1$ al $N$, y las aristas están numeradas del $1$ al $N-1$. Inicialmente, todos los vértices son de color negro.

Escriba un programa que realice las dos consultas siguientes:

• 1 i: Cambia el color del vértice $i$. (blanco $\to$ negro, negro $\to$ blanco)
• 2 u: Cuenta el número de vértices $v$ conectados con $u$. Dos vértices están conectados si todos los vértices en el camino que los une tienen el mismo color.

Entrada

La primera línea contiene $N$ ($2 \le N \le 100{,}000$).

Las siguientes $N-1$ líneas contienen los dos vértices $u$ y $v$ conectados por la arista $i$.

La siguiente línea contiene el número de consultas $M$ ($1 \le M \le 100{,}000$).

Las siguientes $M$ líneas contienen las consultas, una por línea.

Salida

Para cada consulta de tipo 2, imprime el resultado en una línea separada, en orden.

Ejemplos

Entrada 1

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

Salida 1

5
1

Entrada 2

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

Salida 2

7
3
3