406781: GYM102538 G 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, 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!

The first line of input contains three integers $$$n, m, k$$$ ($$$1 \leq n \leq 100\,000, n-1 \leq m \leq 200\,000, 0 \leq k \leq 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 \leq u_i, v_i \leq 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 \leq q \leq 200\,000$$$): the number of queries.

The next $$$q$$$ lines contain the description of edges. The $$$i$$$-th of them contain two integers $$$t_i, v_i$$$ ($$$1 \leq t_i \leq 2, 1 \leq v_i \leq 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.

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

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

0
1
2
1
0

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

2
2