거대 펭귄

펭수는 유명한 거대한 한국 펭귄이다. 그는 매우 무례하고 노래를 좋아한다.

이번에도 펭수는 그래프 질의를 처리하고 있다.

펭수에게는 연결된 무방향 그래프가 있다. 각 정점은 정점이 중복되지 않는 단순 사이클을 최대 $k$개만 지난다.

펭수는 다음 두 종류의 질의에 답하고 싶어 한다.

• 정점 $v$에 표시를 한다.
• 정점 $v$에서 가장 가까운 표시된 정점까지의 거리를 구한다. 이 질의가 주어질 때에는 표시된 정점이 하나 이상 있다고 보장된다.

펭수는 매우 게을러서 낮잠을 자기로 했고, 그래서 당신에게 이 질의들을 처리해 달라고 부탁했다. 그가 깨기 전에 끝내지 못하면 그는 당신을 괴롭힐 테니 서둘러 주기 바란다.

첫 줄에 세 정수 $n$, $m$, $k$가 주어진다 ($1 \le n \le 100000$, $n-1 \le m \le 200000$, $0 \le k \le 10$). 각각 정점의 수, 간선의 수, 한 정점을 지나는 정점 단순 사이클의 최대 개수이다.

이어서 $m$개의 줄에 각각 두 정수 $u_i$, $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$)가 주어지며, $u_i$와 $v_i$를 잇는 간선을 뜻한다. 다중 간선은 없고, 그래프는 연결되어 있으며, 각 정점은 최대 $k$개의 정점 단순 사이클에만 속한다고 보장된다.

다음 줄에는 질의의 수 $q$ ($1 \le q \le 200000$)가 주어진다.

이어서 $q$개의 줄에 각각 두 정수 $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$인 각 질의에 대해, 가장 가까운 표시된 정점까지의 거리를 한 줄에 하나씩 출력한다.