有向图与查询

题目描述

给定一个有 $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$ 时的答案。

样例

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

2
3
-1

对 $x = 1$,从顶点 1 经第 1 条边到顶点 2 的路径费用为 $2$,这是最小值。

对 $x = 2$,从顶点 2 经第 2 条边到顶点 3、再经第 3 条边到顶点 1 的路径费用为 $3$,这是最小值。

对 $x = 3$,不存在从顶点 1 到顶点 4 的路径,因此输出 -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$
• 输入中的所有值均为整数。