#abc287h. [abc287_h]Directed Graph and Query

[abc287_h]Directed Graph and Query

問題文

NN 頂点 MM 辺の有向グラフがあります。頂点には 11 から NN までの番号が付いており、ii 番目の有向辺は頂点 aia_i から頂点 bib_i へと結ばれています。

また、このグラフ上の経路について、コストを次のように定めます。

  • 経路上の頂点(始点・終点を含む)の番号の最大値

x=1,2,ldots,Qx=1,2,\\ldots,Q に対して次の問題を解いてください。

  • 頂点 sxs_x から頂点 txt_x への経路のコストの最小値を求めよ。ただし、そのような経路が一つも存在しない場合は代わりに -1 と出力せよ。

なお、入力の量が多くなる場合があるので、高速な方法で入出力を行うことを推奨します。

制約

  • 2leqNleq20002 \\leq N \\leq 2000
  • 0leqMleqN(N1)0 \\leq M \\leq N(N-1)
  • 1leqai,bileqN1 \\leq a_i,b_i \\leq N
  • aineqbia_i \\neq b_i
  • ineqji \\neq j ならば (ai,bi)neq(aj,bj)(a_i,b_i) \\neq (a_j,b_j)
  • 1leqQleq1041 \\leq Q \\leq 10^4
  • 1leqsi,tileqN1 \\leq s_i,t_i \\leq N
  • sineqtis_i \\neq t_i
  • 入力はすべて整数

入力

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

NN MM a1a_1 b1b_1 vdots\\vdots aMa_M bMb_M QQ s1s_1 t1t_1 vdots\\vdots sQs_Q tQt_Q

出力

QQ 行出力せよ。
ii 行目には x=ix=i に対する出力をせよ。


入力例 1

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

出力例 1

2
3
-1

x=1x=1 に対しては、11 番目の辺を通って頂点 11 から頂点 22 へ行く経路のコストが 22 であり、これが最小です。
x=2x=2 に対しては、22 番目の辺を通って頂点 22 から頂点 33 へ、そして 33 番目の辺を通って頂点 33 から頂点 11 へ行く経路のコストが 33 であり、これが最小です。
x=3x=3 に対しては、頂点 11 から頂点 44 への経路が存在しないため -1 と出力します。