Giant Penguin

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. Each vertex lies on at most $k$ vertex-simple cycles.

He wants to answer two types of queries.

• Mark a vertex $v$.
• Find the distance from vertex $v$ to the closest marked vertex. At least one vertex is marked whenever this query is asked.

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

The first line contains three integers $n$, $m$, and $k$ ($1 \le n \le 100000$, $n-1 \le m \le 200000$, $0 \le k \le 10$): the number of vertices, the number of edges, and the maximum number of vertex-simple cycles that pass through one vertex.

The next $m$ lines each contain two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), denoting an edge between $u_i$ and $v_i$. 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 200000$): the number of queries.

The next $q$ lines each contain two integers $t_i$ and $v_i$ ($1 \le t_i \le 2$, $1 \le v_i \le n$). If $t_i = 1$, mark vertex $v_i$. Vertex $v_i$ was not marked before. If $t_i = 2$, print the distance from $v_i$ to the closest marked vertex. At least one vertex is marked at that time.

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