← 返回题目列表

AtCoder · abc287_h

Ex. 有向图和查询

中文机器翻译题面 查看原题

分数: 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
  • If 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- 从顶点开始的 rd 边 3 到顶点 1 的成本为 3,这是最小值。
对于 x=3,没有从顶点开始的路径 1 到顶点 4,所以 -1 。