Pengsoo to znany wielki koreański pingwin. Jest bardzo niegrzeczny i uwielbia śpiewać. Tym razem Pengsoo wykonuje zapytania na grafie. Posiada spójny graf nieskierowany, w którym każdy wierzchołek leży na co najwyżej $k$ cyklach prostych (w sensie wierzchołkowym). Chce odpowiedzieć na dwa rodzaje zapytań:

• Oznacz pewien wierzchołek $v$.
• Znajdź najbliższy oznaczony wierzchołek od wierzchołka $v$ (gwarantuje się, że w momencie zadania zapytania tego typu istnieje co najmniej jeden oznaczony wierzchołek).

Pengsoo jest bardzo leniwy i postanowił uciąć sobie drzemkę, więc prosi cię o wykonanie tych zapytań. Jeśli nie zdążysz przed jego przebudzeniem, będzie ci dokuczał, więc działaj szybko!

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $n, m, k$ ($1 \le n \le 100\,000, n - 1 \le m \le 200\,000, 0 \le k \le 10$): liczbę wierzchołków, krawędzi oraz największą liczbę cykli prostych, które mogą przechodzić przez jeden wierzchołek.

Kolejne $m$ linii zawiera opis krawędzi. $i$-ta z nich zawiera dwie liczby całkowite $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), oznaczające krawędź między wierzchołkami $u_i$ oraz $v_i$.

Gwarantuje się, że nie ma krawędzi wielokrotnych, graf jest spójny, a każdy wierzchołek leży na co najwyżej $k$ cyklach prostych.

Następna linia zawiera jedną liczbę całkowitą $q$ ($1 \le q \le 200\,000$): liczbę zapytań.

Kolejne $q$ linii zawiera opis zapytań. $i$-ta z nich zawiera dwie liczby całkowite $t_i, v_i$ ($1 \le t_i \le 2, 1 \le v_i \le n$).

Jeśli $t_i = 1$, oznacz wierzchołek $v_i$. Gwarantuje się, że ten wierzchołek nie był wcześniej oznaczony.

Jeśli $t_i = 2$, znajdź odległość do najbliższego oznaczonego wierzchołka od $v_i$. Gwarantuje się, że istnieje co najmniej jeden oznaczony wierzchołek.

Wyjście

Dla każdego zapytania z $t_i = 2$ wypisz odległość do najbliższego oznaczonego wierzchołka.

Przykład

Wejście 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

Wyjście 1

0
1
2
1
0

Wejście 2

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

Wyjście 2

2
2