题目描述

一套通信系统由 n 个站点和 m 条双向链路组成，任意两个站点之间都可以通过若干链路互相到达。系统的拓扑结构比较稀疏：保证每个站点至多位于 k 个点不重复的简单环上。

系统运行过程中，会不断发生两类事件：

• 在某个尚未安装信标的站点安装一个信标；
• 查询某个站点到最近信标站点的最短链路距离。

每次进行查询时，保证系统中已经至少有一个站点安装了信标。请你依次处理所有事件。

输入格式

第一行包含三个整数 n, m, k，分别表示站点数、链路数，以及任意一个站点最多属于多少个点简单环。

接下来 m 行，每行包含两个整数 u_i, v_i，表示站点 u_i 与站点 v_i 之间有一条双向链路。

保证图连通，没有自环和重边，并且每个顶点属于的点简单环数量不超过 k。

接下来一行包含一个整数 q，表示事件数量。

接下来 q 行，每行包含两个整数 t_i, v_i：

• 若 t_i = 1，表示在站点 v_i 安装信标。保证该站点此前没有安装过信标；
• 若 t_i = 2，表示查询站点 v_i 到最近信标站点的距离。保证此时至少有一个站点已安装信标。

输出格式

对于每个 t_i = 2 的事件，输出一行一个整数，表示被查询站点到最近信标站点的最短路长度。

数据范围

• 1 <= n <= 100000
• n - 1 <= m <= 200000
• 0 <= k <= 10
• 1 <= q <= 200000
• 1 <= u_i, v_i <= n

样例

样例 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