Pengsooは韓国で有名な巨大なペンギンです。彼は非常に無礼で、歌うことが大好きです。 今回、Pengsooはグラフに対するクエリを実行しています。 彼は連結な無向グラフを持っており、各頂点は高々 $k$ 個の頂点単純サイクル上に存在します。 彼は以下の2種類のクエリに答える必要があります。

• ある頂点 $v$ に印を付ける。
• 頂点 $v$ に最も近い印が付けられた頂点を見つける（この種類のクエリが与えられるとき、少なくとも1つの頂点に印が付けられていることが保証されます）。

Pengsooは非常に怠け者で、昼寝をすることにしたため、あなたにこれらのクエリを実行するように頼みました。彼が目を覚ますまでに成功しなければ、彼はあなたをいじめるでしょう。ですから、素早く行動してください！

入力

入力の最初の行には、3つの整数 $n, m, k$ ($1 \le n \le 100\,000, n - 1 \le m \le 200\,000, 0 \le k \le 10$) が含まれます。これらはそれぞれ、頂点数、辺数、および1つの頂点を通る可能性のある頂点単純サイクルの最大数です。

続く $m$ 行には、辺の説明が含まれます。$i$ 番目の行には2つの整数 $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$ 番目の行には2つの整数 $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$ から最も近い印が付けられた頂点までの距離を求めます。少なくとも1つの頂点に印が付けられていることが保証されます。

出力

$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