Пенгсу — известный гигантский корейский пингвин. Он очень грубый и любит петь. В этот раз Пенгсу выполняет запросы на графе. У него есть связный неориентированный граф, в котором каждая вершина принадлежит не более чем $k$ простым циклам. Он хочет отвечать на запросы двух типов:

• Отметить некоторую вершину $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

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