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

Escribe un programa que realice las siguientes dos consultas:

• 1 i: Cambia el color del vértice $i$ (blanco $\to$ negro, negro $\to$ blanco).
• 2 v: Imprime la distancia más cercana entre todos los vértices blancos $u$ y $v$. En este caso, $u$ y $v$ pueden ser el mismo. Si $v$ es blanco, la respuesta es $0$. Si no hay vértices blancos en el árbol, imprime $-1$.

Entrada

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

Las siguientes $N-1$ líneas contienen dos números de vértice $u$ y $v$ que conecta la $i$-ésima arista.

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

Imprime los resultados de cada consulta de tipo $2$ en orden, uno por línea.

Ejemplos

Entrada 1

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

Salida 1

2
2
2
3
0