最小代价

题目描述

有一个包含 $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$ 的答案。

输入输出样例 #1

输入 #1

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

输出 #1

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$
• 所有输入均为整数

样例解释 1

对于 $x=1$，可以通过第 1 条边从顶点 $1$ 到顶点 $2$，路径代价为 $2$，这是最小值。
对于 $x=2$，可以通过第 2 条边从顶点 $2$ 到顶点 $3$，再通过第 3 条边从顶点 $3$ 到顶点 $1$，路径代价为 $3$，这是最小值。
对于 $x=3$，不存在从顶点 $1$ 到顶点 $4$ 的路径，因此输出 $-1$。