Pengsoo es un conocido pingüino gigante coreano. Es muy grosero y le encanta cantar.

En esta ocasión, Pengsoo está realizando consultas sobre grafos.

Tiene un grafo conexo no dirigido, donde cada vértice pertenece a lo sumo a $k$ ciclos simples de vértices.

Él quiere responder a dos tipos de consultas:

• Marcar algún vértice $v$.
• Encontrar el vértice marcado más cercano al vértice $v$ (se garantiza que cuando se realiza una consulta de este tipo, existe al menos un vértice marcado).

Pengsoo es muy perezoso y ha decidido tomar una siesta, por lo que te pide que realices estas consultas. Si no tienes éxito para cuando él despierte, te molestará, ¡así que actúa rápido!

Entrada

La primera línea de la entrada contiene tres enteros $n, m, k$ ($1 \le n \le 100\,000$, $n - 1 \le m \le 200\,000$, $0 \le k \le 10$): el número de vértices, aristas y el mayor número de ciclos simples de vértices que pueden pasar por un vértice.

Las siguientes $m$ líneas contienen la descripción de las aristas. La $i$-ésima línea contiene dos enteros $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), que denotan una arista entre los vértices $u_i$ y $v_i$.

Se garantiza que no hay aristas múltiples, que el grafo es conexo y que cada vértice pertenece a lo sumo a $k$ ciclos simples de vértices.

La siguiente línea contiene un entero $q$ ($1 \le q \le 200\,000$): el número de consultas.

Las siguientes $q$ líneas contienen la descripción de las consultas. La $i$-ésima línea contiene dos enteros $t_i, v_i$ ($1 \le t_i \le 2, 1 \le v_i \le n$).

Si $t_i = 1$, marca el vértice $v_i$. Se garantiza que este vértice no estaba marcado anteriormente.

Si $t_i = 2$, encuentra la distancia al vértice marcado más cercano desde $v_i$. Se garantiza que existe al menos un vértice marcado.

Salida

Para cada consulta con $t_i = 2$, imprime la distancia al vértice marcado más cercano.

Ejemplos

Entrada 1

5 4 0
1 2
2 3
3 4
4 5
7
1 1
1 5
2 1
2 2
2 3
2 4
2 5

Salida 1

0
1
2
1
0

Entrada 2

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

Salida 2

2
2