Ex - Directed Graph and Query Editorial /

Time Limit: 4.5 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点 M 辺の有向グラフがあります。頂点には 1 から N までの番号が付いており、i 番目の有向辺は頂点 a_i から頂点 b_i へと結ばれています。

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

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

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

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

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

制約

  • 2 \leq N \leq 2000
  • 0 \leq M \leq N(N-1)
  • 1 \leq a_i,b_i \leq N
  • a_i \neq b_i
  • i \neq j ならば (a_i,b_i) \neq (a_j,b_j)
  • 1 \leq Q \leq 10^4
  • 1 \leq s_i,t_i \leq N
  • s_i \neq t_i
  • 入力はすべて整数

入力

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

N M
a_1 b_1
\vdots
a_M b_M
Q
s_1 t_1
\vdots
s_Q t_Q

出力

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

入力例 1

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

出力例 1

2
3
-1

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

Score : 600 points

Problem Statement

There is a directed graph with N vertices and M edges. The vertices are numbered 1 through N, and the i-th directed edge goes from vertex a_i to vertex b_i.

The cost of a path on this graph is defined as:

  • the maximum index of a vertex on the path (including the initial and final vertices).

Solve the following problem for each x=1,2,\ldots,Q.

  • Find the minimum cost of a path from vertex s_x to vertex t_x. If there is no such path, print -1 instead.

The use of fast input and output methods is recommended because of potentially large input and output.

Constraints

  • 2 \leq N \leq 2000
  • 0 \leq M \leq N(N-1)
  • 1 \leq a_i,b_i \leq N
  • a_i \neq b_i
  • If i \neq j, then (a_i,b_i) \neq (a_j,b_j).
  • 1 \leq Q \leq 10^4
  • 1 \leq s_i,t_i \leq N
  • s_i \neq t_i
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M
a_1 b_1
\vdots
a_M b_M
Q
s_1 t_1
\vdots
s_Q t_Q

Output

Print Q lines.
The i-th line should contain the answer for x=i.

Sample Input 1

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

Sample Output 1

2
3
-1

For x=1, the path via the 1-st edge from vertex 1 to vertex 2 has a cost of 2, which is the minimum.
For x=2, the path via the 2-nd edge from vertex 2 to vertex 3 and then via the 3-rd edge from vertex 3 to vertex 1 has a cost of 3, which is the minimum.
For x=3, there is no path from vertex 1 to vertex 4, so -1 should be printed.