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

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

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.

Input

Output

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


样例输入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

加入题单

上一题 下一题 算法标签: