分数: 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 。