Pengsoo est un célèbre manchot géant coréen. Il est très impoli et adore chanter.

Cette fois-ci, Pengsoo effectue des requêtes sur un graphe.

Il possède un graphe connexe non orienté, où chaque sommet appartient à au plus $k$ cycles simples.

Il souhaite répondre à deux types de requêtes :

• Marquer un sommet $v$.
• Trouver le sommet marqué le plus proche du sommet $v$ (il est garanti que lorsqu'une requête de ce type est posée, il existe au moins un sommet marqué).

Pengsoo est très paresseux et a décidé de faire une sieste, il vous demande donc d'effectuer ces requêtes. Si vous ne réussissez pas avant qu'il ne se réveille, il vous brutalisera, alors agissez rapidement !

Entrée

La première ligne de l'entrée contient trois entiers $n, m, k$ ($1 \le n \le 100\,000$, $n - 1 \le m \le 200\,000$, $0 \le k \le 10$) : le nombre de sommets, d'arêtes et le nombre maximal de cycles simples passant par un sommet.

Les $m$ lignes suivantes contiennent la description des arêtes. La $i$-ième ligne contient deux entiers $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), désignant une arête entre les sommets $u_i$ et $v_i$.

Il est garanti qu'il n'y a pas d'arêtes multiples, que le graphe est connexe et que chaque sommet appartient à au plus $k$ cycles simples.

La ligne suivante contient un entier $q$ ($1 \le q \le 200\,000$) : le nombre de requêtes.

Les $q$ lignes suivantes contiennent la description des requêtes. La $i$-ième ligne contient deux entiers $t_i, v_i$ ($1 \le t_i \le 2$, $1 \le v_i \le n$).

Si $t_i = 1$, marquez le sommet $v_i$. Il est garanti que ce sommet n'a pas été marqué auparavant.

Si $t_i = 2$, trouvez la distance entre $v_i$ et le sommet marqué le plus proche. Il est garanti qu'il existe au moins un sommet marqué.

Sortie

Pour chaque requête avec $t_i = 2$, affichez la distance au sommet marqué le plus proche.

Exemples

Entrée 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

Sortie 1

0
1
2
1
0

Entrée 2

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

Sortie 2

2
2