CF685E Travelling Through the Snow Queen's Kingdom

Gerda 正在前往雪之女王的宫殿。 道路网络由 $n$ 个路口和 $m$ 条双向道路组成。道路编号为 $1$ 到 $m$。雪之女王对道路施加了强大的魔法，改变了那里天气的状况。现在，如果 Gerda 在时刻不超过 $i$ 的时刻踏上第 $i$ 条道路，她将恰好在时刻 $i$ 离开这条道路。如果她在时刻大于 $i$ 的时候才踏上第 $i$ 条道路，她将永远停留在这条路上，无法前进。 Gerda 在时刻 $l$ 从编号为 $s$ 的路口出发，前往雪之女王的宫殿，该宫殿位于编号为 $t$ 的路口。此外，她必须在时刻 $r$（或更早）到达那里，在女王抵达之前。 给定道路网络的描述，对于 $q$ 个询问，询问分别给出 $l_i$，$r_i$，$s_i$ 和 $t_i$，判断 Gerda 是否有可能按时到达宫殿。

输入的第一行包含整数 $n$、$m$ 和 $q$（$2 \leq n \leq 1000$，$1 \leq m, q \leq 200000$），分别表示雪之女王王国的路口数、道路数以及需要回答的问题数。 接下来的 $m$ 行，第 $i$ 行包含两个整数 $v_i$ 和 $u_i$（$1 \leq v_i, u_i \leq n$，$v_i \neq u_i$），表示第 $i$ 条道路连接的两个路口编号。通过这条道路，可以从 $v_i$ 到 $u_i$，也可以从 $u_i$ 到 $v_i$。每对路口之间可能会有多条道路。 最后 $q$ 行，每行包含四个整数 $l_i$、$r_i$、$s_i$ 和 $t_i$（$1 \leq l_i \leq r_i \leq m$，$1 \leq s_i, t_i \leq n$，$s_i \neq t_i$），分别表示 Gerda 出发的时刻、她必须到达宫殿的最迟时刻、起点路口编号和宫殿所在的路口编号。

对于每个询问，如果 Gerda 能够及时到达雪之女王的宫殿（不晚于 $r_i$ 的时刻），输出 "Yes"（不带引号）；否则输出 "No"（不带引号）。

由 ChatGPT 5 翻译