E - 瞬間移動装置 Editorial /

Time Limit: 2 sec / Memory Limit: 512 MB

配点 : 1400 点

問題文

高橋王国には 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

入力

入力は以下の形式で標準入力から与えられる。

N M Q
a_1 b_1
a_2 b_2
:
a_M b_M
c_1 d_1
c_2 d_2
:
c_Q d_Q

出力

i 行目には，i 番目の質問に対する答えを出力せよ．ただし，都市 c_i から都市 d_i まで瞬間移動装置を乗り継いで移動することが不可能なときは，代わりに -1 を出力せよ．

入力例 1

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

出力例 1

2
1
2
3

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

入力例 2

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

出力例 2

1
-1