E - 瞬間移動装置 /

Time Limit: 2 sec / Memory Limit: 512 MB

配点 : 1400

問題文

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

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

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

  • i 番目の質問では,c_id_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