102877: [AtCoder]ABC287 Ex - Directed Graph and Query

Problem Statement

There is a directed graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the $i$-th directed edge goes from vertex $a_i$ to vertex $b_i$.

The cost of a path on this graph is defined as:

• the maximum index of a vertex on the path (including the initial and final vertices).

Solve the following problem for each $x=1,2,\ldots,Q$.

• Find the minimum cost of a path from vertex $s_x$ to vertex $t_x$. If there is no such path, print -1 instead.

The use of fast input and output methods is recommended because of potentially large input and output.

Constraints

• $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$
• If $i \neq j$, then $(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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$
$Q$
$s_1$ $t_1$
$\vdots$
$s_Q$ $t_Q$

Output

Print $Q$ lines.
The $i$-th line should contain the answer for $x=i$.

Sample Input 1

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

Sample Output 1

2
3
-1

For $x=1$, the path via the $1$-st edge from vertex $1$ to vertex $2$ has a cost of $2$, which is the minimum.
For $x=2$, the path via the $2$-nd edge from vertex $2$ to vertex $3$ and then via the $3$-rd edge from vertex $3$ to vertex $1$ has a cost of $3$, which is the minimum.
For $x=3$, there is no path from vertex $1$ to vertex $4$, so -1 should be printed.

问题描述

有一个有向图，有$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。