P17890 [ICPC 2026 Nanchang I] Tourist

题目描述

构造王国是著名的旅游胜地,每年都会吸引数以万计的游客前来旅游。王国由 $n$ 座城镇和 $m$ 条单向道路组成,每条道路长度均为 $1$。保证初始的 $m$ 条道路中没有重复的道路,也没有从一座城镇通向自身的道路。 后来由于旅游业的持续繁荣,构造王国决定扩建道路。从第 $1$ 天开始,在接下来的 $k$ 天里,每天都会新建一条从 $x$ 到 $y$ 的单向道路。由于规划不当,可能出现修建一条已经存在的道路,或者修建一条自己到自己的道路的情况。 枫蜜是一位任性的旅行者,她有 $q$ 个旅行愿望和一个心愿距离 $w$。每个愿望有一个起点 $s$ 和终点 $t$($s_i$ 和 $t_i$ 可能相同)。她想知道,对于每个愿望,最早在第几天的时候,可以从城镇 $s$ 出发,在允许多次经过城镇和道路的前提下,恰好走 $w$ 的距离到达城镇 $t$,或报告无法实现。请你帮她解决这个问题。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 200$, $1 \le m \le n(n-1)$),表示城镇数量和初始道路数量。 接下来 $m$ 行,每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$),表示一条从 $u_i$ 到 $v_i$ 的有向道路。 接下来一行包含一个整数 $k$ ($1 \le k \le n^2$),表示接下来要修建的道路数量。 接下来 $k$ 行,每行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le n$),表示第 $i$ 天新建一条从 $x_i$ 到 $y_i$ 的有向道路。 接下来一行包含两个整数 $q$ 和 $w$ ($1 \le q \le n^2$, $1 \le w \le 10^9$),分别表示愿望数量和心愿距离。 接下来 $q$ 行,每行包含两个整数 $s_i$ 和 $t_i$ ($1 \le s_i, t_i \le n$),描述第 $i$ 个愿望的起点和终点。

输出格式

对于每个愿望,输出一个整数,表示最早能够实现该愿望的天数(即在那一天修建完道路后,恰好存在一条长度为 $w$ 的路径从 $s$ 走到 $t$)。如果永远无法实现,输出 $-1$。

说明/提示

在样例中,心愿距离 $w = 8$。 - 对于第一个愿望,可以证明无法实现。 - 对于第二个愿望,在修建了 $4 \to 5$ 和 $5 \to 5$ 这两条道路后,可以沿着城镇序列 $[5, 5, 5, 5, 5, 5, 5, 5, 5]$ 行走,从而到达终点。 - 对于第三个愿望,初始时即可沿着城镇序列 $[1, 3, 1, 3, 1, 3, 1, 3, 1]$ 走到终点。 - 对于第四个愿望,在修建了 $4 \to 5$ 和 $5 \to 5$ 这两条道路后,可以沿着城镇序列 $[4, 5, 5, 5, 5, 5, 5, 5, 5]$ 走到终点。 - 对于第五个愿望,在修建了 $4 \to 5$, $5 \to 5$, $2 \to 5$, $5 \to 6$ 这些道路后,可以沿着城镇序列 $[4, 5, 5, 5, 5, 5, 5, 5, 6]$ 走到终点。