← 返回题目列表

AtCoder · yahoo_procon2017_final_e

E. 瞬间移动装置

中文机器翻译题面 查看原题

配点 : 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