펭수는 잘 알려진 거대한 한국 펭귄입니다. 그는 매우 무례하고 노래 부르는 것을 좋아합니다.

이번에 펭수는 그래프 쿼리를 수행하고 있습니다.

그는 연결된 무방향 그래프를 가지고 있으며, 각 정점은 최대 $k$개의 정점 단순 사이클(vertex-simple cycle)에 포함됩니다.

그는 두 가지 유형의 쿼리에 답하고자 합니다.

• 어떤 정점 $v$를 표시합니다.
• 정점 $v$에서 가장 가까운 표시된 정점을 찾습니다 (이 유형의 쿼리가 주어질 때는 항상 최소한 하나의 표시된 정점이 있음이 보장됩니다).

펭수는 매우 게을러서 낮잠을 자기로 결정했으므로, 여러분에게 이 쿼리들을 수행해 달라고 요청했습니다. 그가 잠에서 깰 때까지 성공하지 못하면 그는 여러분을 괴롭힐 것이니, 빨리 행동하세요!

입력

입력의 첫 번째 줄에는 세 정수 $n, m, k$ ($1 \le n \le 100\,000, n - 1 \le m \le 200\,000, 0 \le k \le 10$)가 주어집니다. 이는 각각 정점의 수, 간선의 수, 그리고 하나의 정점을 지날 수 있는 정점 단순 사이클의 최대 개수를 의미합니다.

다음 $m$개의 줄에는 간선에 대한 설명이 주어집니다. $i$번째 줄에는 두 정수 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)가 주어지며, 이는 정점 $u_i$와 $v_i$ 사이의 간선을 의미합니다.

다중 간선은 없으며, 그래프는 연결되어 있고, 각 정점은 최대 $k$개의 정점 단순 사이클에 포함됨이 보장됩니다.

다음 줄에는 쿼리의 개수를 나타내는 정수 $q$ ($1 \le q \le 200\,000$)가 주어집니다.

다음 $q$개의 줄에는 쿼리에 대한 설명이 주어집니다. $i$번째 줄에는 두 정수 $t_i, v_i$ ($1 \le t_i \le 2, 1 \le v_i \le n$)가 주어집니다.

$t_i = 1$이면, 정점 $v_i$를 표시합니다. 이 정점은 이전에 표시된 적이 없음이 보장됩니다.

$t_i = 2$이면, $v_i$에서 가장 가까운 표시된 정점까지의 거리를 찾습니다. 최소한 하나의 표시된 정점이 있음이 보장됩니다.

출력

$t_i = 2$인 각 쿼리에 대해, 가장 가까운 표시된 정점까지의 거리를 출력합니다.

예제

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