問題文

アライグマさんたちが故郷に帰省しようとしています。

アライグマさんが住む国は $N$ 個の街と, 異なる街同士をつなぐ $M$ 本の道からなり, それぞれの街には $1$ から $N$ の番号が割り振られています。 $i$ 番目の道を使って街 $A_i$ と $B_i$ の間を双方向に移動することが可能です。

ここで $Q$ 個のクエリの情報が時系列順に与えられます。 $j$ 番目のクエリは以下の $2$ 種類のうちのいずれかです。

• クエリ $1$: 街 $U_j$ に価値 $W_j$ の獲物が $1$ 匹出現する。この獲物は街 $U_j$ を訪れることにより捕まえることができる。 出現する獲物の価値 $W_j$ はそれぞれ異なる。
• クエリ $2$: 街 $S_j$ にいる $1$ 匹のアライグマさんが街 $T_j$ に帰省する。 同じ道を何度も通ると天敵に狙われるので, 同じ道を複数回使うことはできない。
  このとき, 帰省の途中(街 $S_j$, $T_j$ を含む) に捕まえることができる価値が最大の獲物を $1$ 匹お土産として捕まえる。 途中で街 $T_j$ を通過しても, 最終的に街 $T_j$ に到達できれば良い。 捕まえられる獲物が存在しない場合は仕方がないので手ぶらで帰省する。
  捕まえた獲物はなくなるので, この獲物を再び捕まえることはできない。

それぞれのアライグマさんがお土産として捕まえた獲物の価値が気になりました。 それぞれのクエリ $2$ について, 捕まえた獲物の価値を調べてください。

入力

$N$ $M$ $Q$
$A_1$ $B_1$
$A_2$ $B_2$
:
$A_M$ $B_M$
$Quer{y}_1$
$Quer{y}_2$
:
$Quer{y}_Q$

$1$ 行目に街の個数 $N(2\le N\le 100000)$, 道の本数 $M(1\le M\le 200000)$, クエリの個数 $Q(1\le Q\le 200000)$ が与えられます。

$2$ 行目から $M$ 行にかけて存在する道の情報が与えられます。 このうち $i$ 行目は $i$ 番目の道を使って街 $A_i$ と街 $B_i(1\le A_i<B_i\le N)$ の間を双方向に移動できることを表します。同じ $A_i,B_i$ の組が与えられることはありません。
また存在する道を使ってどの街からどの街にも移動できることが保証されています。

その後 $Q$ 行にかけてクエリの情報が時系列順に与えられます。 このうち $j$ 行目は $j$ 番目のクエリの情報であり, 以下のいずれかの形式で与えられます。

$1$ $U_j$ $W_j$

$2$ $S_j$ $T_j$

• 先頭の値が $1$ のとき, クエリ $1$ であることを表します。街 $U_j(1\le U_j\le N)$ に価値 $W_j(1\le W_j\le {10}^9)$ の獲物が新たに $1$ 匹出現することを意味し, 価値 $W_j$ は各クエリで異なることが保証されます。
• 先頭の値が $2$ のとき, クエリ $2$ であることを表します。$1$ 匹のアライグマさんが街 $S_j$ から街 $T_j(1\le S_j,T_j\le N)$ に帰省することを意味し, $S_j\ne T_j$ が保証されます。

出力

出力の行数は, クエリ $2$ の数と一致します。

クエリ $2$ が与えられる順に, そのアライグマさんが捕まえたお土産の獲物の価値を出力してください。 手ぶらで帰省した場合は $-1$ を出力してください。

サンプル

サンプル1

入力サンプルをコピー

入力

4 4 7
1 2
2 3
3 4
2 4
2 1 2
1 1 13
1 1 133
1 3 1333
2 1 2
2 4 3
2 4 1

出力

-1
1333
-1
133

与えられるグラフは下図の通りです。

• $1$ 番目のクエリでは街 $1$ から街 $4$ に移動します。獲物はどこにも存在しないので $-1$ を出力します。
• $2$ 番目のクエリでは街 $1$ に価値 $13$ の獲物が出現します。
• $3$ 番目のクエリでは街 $1$ に価値 $133$ の獲物が出現します。
• $4$ 番目のクエリでは街 $3$ に価値 $1333$ の獲物が出現します。
• $5$ 番目のクエリでは街 $1$ から街 $2$ に移動します。街 $1$ にいる価値 $13,133$, 街 $3$ にいる $1333$ の獲物のうち $1$ 匹を捕まえられます。
この中の価値の最大の $1333$ を捕まえるので $1333$ を出力します。例えば以下のように $1\to 2\to 3\to 4\to 2$ の順で移動します。

• $6$ 番目のクエリでは街 $4$ から街 $3$ に移動します。街 $1$ に獲物が存在しますが, 街 $4$ から街 $1$ を訪れて街 $3$ に移動するには同じ道を複数回通る必要があるためできません。 $-1$ を出力します。
• $7$ 番目のクエリででは 街 $4$ から街 $1$ に移動します。街 $1$ にいる価値 $13,133$ の獲物のうち, 大きい方を捕まえるため $133$ を出力します。
  

4 3 7
1 2
2 3
2 4
2 1 2
1 1 13
1 1 133
1 3 1333
2 1 4
2 4 3
2 4 1

-1
133
1333
13