题目描述

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

示例输入 1

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

示例输出 1

2
3
-1

对于 $x=1$，从顶点 $1$ 经过第 $1$ 条边到达顶点 $2$ 的路径的成本为 $2$，为最小值。
对于 $x=2$，从顶点 $2$ 经过第 $2$ 条边到达顶点 $3$，然后经过第 $3$ 条边从顶点 $3$ 到达顶点 $1$ 的路径的成本为 $3$，为最小值。
对于 $x=3$，从顶点 $1$ 到顶点 $4$ 不存在路径，因此应打印 -1。