CF238E Meeting Her

Urpal 住在一个大城市。他今晚准备去见他的恋人。 这座城市有 $n$ 个路口，编号从 $1$ 到 $n$。路口之间通过 $m$ 条单向街道相连，所有道路长度相等。Urpal 住在编号为 $a$ 的路口，约会安排在编号为 $b$ 的餐厅。他想要乘坐公共交通工具前往 $b$ 路口。 有 $k$ 家公交公司。在每一秒开始时，第 $i$ 家公司的公交车会随机选择一条从路口 $s_i$ 到路口 $t_i$ 的最短路径，并按照该路径经过。有可能 $s_i$ 到 $t_i$ 没有路径，这种情况下该公司不会发车。如果公交车经过 Urpal 所在的路口，他可以上车，并且可以在经过的任意一个路口下车。 现在 Urpal 想知道，是否有可能在有限时间内通过公共交通前往约会地点（旅行时间为所经过道路长度之和），以及在最坏情况下，他至少需要乘坐多少辆公交车。 在任何时刻，Urpal 只知道自己和约会地点的位置。当他上车时，他只知道所乘公交的公司编号。当然，Urpal 知道整个城市的地图以及每家公司的 $ (s_i, t_i) $ 对。 注意，Urpal 并不知道公交车的速度。

输入的第一行包含四个整数：$n$、$m$、$a$、$b$，满足 $2 \leq n \leq 100$，$0 \leq m \leq n \cdot (n-1)$，$1 \leq a, b \leq n$，$a \neq b$。 接下来 $m$ 行，每行两个整数 $u_i$ 和 $v_i$，表示一条从 $u_i$ 到 $v_i$ 的有向道路，$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$。所有道路互不重复。 接下来一行包含一个整数 $k$，满足 $0 \leq k \leq 100$。接下来 $k$ 行，每行两个整数 $s_i$ 和 $t_i$，表示有一条公交线路从 $s_i$ 出发到 $t_i$，$1 \leq s_i, t_i \leq n$，$s_i \neq t_i$。请注意，$s_i$ 到 $t_i$ 之间可能没有路径，这种情况在题目描述中已说明。

输出仅一行，表示在最坏情况下，Urpal 至少需要乘坐的最小公交车数量。如果在最坏情况下无法到达目的地，则输出 $-1$。

由 ChatGPT 5 翻译