시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 5 5 5 100.000%

문제

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 ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi), denoting an edge between vertices ui and vi.

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 ti, vi (1 ≤ ti ≤ 2, 1 ≤ vi ≤ n).

If ti = 1, mark the vertex vi. It is guaranteed that this vertex was not marked before.

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

출력

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

예제 입력 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

예제 출력 1

0
1
2
1
0

예제 입력 2

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

예제 출력 2

2
2