Pengsoo 是一只著名的韩国巨型企鹅。他非常粗鲁且热爱唱歌。

这一次，Pengsoo 正在进行图查询。

他有一个连通的无向图，其中每个顶点位于至多 $k$ 个顶点简单环上。

他想要回答两类查询：

• 标记某个顶点 $v$。
• 找到距离顶点 $v$ 最近的已标记顶点（保证在进行此类查询时，至少存在一个已标记的顶点）。

Pengsoo 非常懒，决定去小睡一会儿，所以他让你来执行这些查询。如果你在他醒来之前没有完成，他会欺负你，所以动作要快！

输入格式

第一行包含三个整数 $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