Pengsoo 是一隻著名的韓國巨型企鵝。他非常粗魯且熱愛唱歌。 這次，Pengsoo 正在執行圖論查詢。 他擁有一個連通的無向圖，其中每個頂點至多位於 $k$ 個頂點簡單環（vertex-simple cycles）上。 他想要回答兩種類型的查詢：

• 標記某個頂點 $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