题目描述

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

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

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

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

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

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

输入格式

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

$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$ に対する出力をせよ。

题目大意

$N$ 点 $M$ 边有向图，结点从 $1$ 到 $N$ 编号，第 $i$ 边连接结点 $a_i, b_i$。

路径的「成本」被定义为：

• 路径上点的最大编号（包括起点和终点）

对 $x = 1,2,\cdots,Q$，解决以下问题：

• 求从点 $s_x$ 到 $t_x$ 的最小「成本」，如果没有从路径，输出 -1。

由于输入和输出量可能很大，建议使用较快速的输入方式。

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

2
3
-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$
• 入力はすべて整数

Sample Explanation 1

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