Hay un árbol (grafo conexo acíclico no dirigido) compuesto por $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 blanco.

Escribe un programa que realice las dos consultas siguientes:

• 1 i: Cambia el color del vértice $i$ (blanco $\to$ negro, negro $\to$ blanco).
• 2 v: Imprime el número del primer vértice negro que se encuentra en el camino desde el vértice $1$ hasta el vértice $v$. Si no existe tal vértice, 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 $u$ y $v$, los vértices que conecta 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 una consulta por línea.

Salida

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

Ejemplos

Entrada

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

Salida

-1
8
-1
2
-1