有向图和查询

分数：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$ 的答案。

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$ 条边从顶点 $3$ 到顶点 $1$ 的路径的代价是 $3$，是最小的。
对于 $x=3$，没有从顶点 $1$ 到顶点 $4$ 的路径，所以应该输出 -1。