18464번 - 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 ≤ n ≤ 100 000, n − 1 ≤ m ≤ 200 000, 0 ≤ k ≤ 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 ≤ u_i, v_i ≤ n, u_i ≠ 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 ≤ q ≤ 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 ≤ t_i ≤ 2, 1 ≤ v_i ≤ 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.