Pengsoo is a well-known giant Korean penguin. He is very rude and loves singing.

This time, Pengsoo is performing graph queries.

He has a connected undirected graph, where each vertex lies on at most $k$ vertex-simple cycles.

He wants to answer two types of queries.

• Mark some vertex $v$.
• Find the closest marked vertex to the vertex $v$ (it is guaranteed that when the query of this type is asked, there is at least one marked vertex).

Pengsoo is very lazy, and has decided to take a nap, so he asks you to perform these queries. If you do not succeed by the time he wakes up, he will bully you, so act quickly!

Input

The first line of input contains three integers $n, m, k$ ($1 \le n \le 100\,000$, $n - 1 \le m \le 200\,000$, $0 \le k \le 10$): the number of vertices, edges, and largest number of vertex-simple cycles that may pass through one vertex.

The next $m$ lines contain the description of edges. The $i$-th of them contain two integers $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), denoting an edge between vertices $u_i$ and $v_i$.

It is guaranteed that there are no multiple edges, the graph is connected, and each vertex lies on at most $k$ vertex-simple cycles.

The next line contains one integer $q$ ($1 \le q \le 200\,000$): the number of queries.

The next $q$ lines contain the description of queries. The $i$-th of them contain two integers $t_i, v_i$ ($1 \le t_i \le 2, 1 \le v_i \le n$).

If $t_i = 1$, mark the vertex $v_i$. It is guaranteed that this vertex was not marked before.

If $t_i = 2$, find the distance to the closest marked vertex from $v_i$. It is guaranteed that there is at least one marked vertex.

Output

For each query with $t_i = 2$, print the distance to the closest marked vertex.

Examples

Input 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

Output 1

0
1
2
1
0

Input 2

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

Output 2

2
2