AT_abc287_h [ABC287Ex] Directed Graph and Query

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

## 限制条件 - $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$。 由 ChatGPT 4.1 翻译