問題文

高橋王国には $N$ 個の都市 $1, 2, ..., N$ があります． どの $2$ つの異なる都市の間にも，それらの都市間を直接結ぶ瞬間移動装置が設けられています． 都市 $x$ と $y$ を結ぶ瞬間移動装置を使うと，都市 $x$ から都市 $y$ へも，都市 $y$ から都市 $x$ へも移動することができます．

しかし現在，都市 $a_i$ と $b_i$ ($i = 1, 2, ..., M$) を直接結ぶ瞬間移動装置は故障しており，使うことができません．

次のような形式の $Q$ 個の質問に答えてください．

• $i$ 番目の質問では，$c_i$ と $d_i$ が与えられる．このとき，都市 $c_i$ から都市 $d_i$ まで瞬間移動装置を乗り継いで移動するためには，最小で何回瞬間移動装置を利用すればよいか？

制約

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq a_i < b_i \leq N$
• $a_i = a_j$ かつ $b_i = b_j$ を満たす異なる $i, j$ の組は存在しない
• $1 \leq c_i < d_i \leq N$

入力例 1Copy

6 7 4
1 2
2 4
2 5
2 6
3 5
3 6
5 6
1 2
2 3
5 6
2 5

出力例 1Copy

2
1
2
3

使える瞬間移動装置は，下図のようになります．図の太線はその都市間を結ぶ瞬間移動装置が使えること，点線は故障していることを表します．

入力例 2Copy

4 4 2
1 3
1 4
2 3
2 4
1 2
1 3

出力例 2Copy

1
-1