← 返回题目列表

Codeforces · 685/E

E. 穿越雪之女王的王国

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

格尔达正在前往冰雪女王的宫殿。

道路网由 n 个交叉口和 m 个双向道路组成。道路编号从 1 到 m。冰雪女王在道路上施加了强大的咒语,以改变那里的天气状况。现在,如果格尔达在小于或等于 i 的时刻踏上道路 i,她将在 i 时刻离开道路。如果她在比i大的时刻踏上这条路i,她就永远呆在那里。

Gerda 在时间 l 的时刻从 s 号路口出发,前往位于 t 号路口的冰雪女王的宫殿。此外,她必须在女王到来之前(或更早)到达那里。

给定道路网络的描述,确定 q 查询 li、ri、si 和 ti 是否可以让 Gerda 按时到达宫殿。

输入

输入的第一行包含整数 n、m 和 q (2 ≤ n ≤ 1000, 1 ≤ m, q ≤ 200 000) — 雪女王王国道路网络中的交叉口数量、道路数量以及您必须回答的查询数量。

以下 m 行中的第 i 行包含道路编号 i 的描述。该描述由两个整数 vi 和 ui (1 ≤ vi, ui ≤ n, vi ≠ ui) 组成——第 i 条道路连接的交叉口的索引。仅使用这条路就可以从 vi 到 ui 以及从 ui 到 vi。每对交叉路口可能会出现多次,这意味着有几条道路连接这对交叉路口。

最后 q 行包含查询描述。它们分别由四个整数 li、ri、si 和 ti 组成(1 ≤ li ≤ ri ≤ m、1 ≤ si、ti ≤ n、si ≠ ti)——Gerda 开始旅程的时刻、允许她到达宫殿的最后时刻、起始路口的索引和宫殿所在路口的索引。

输出

对于每个查询,如果 Gerda 可以准时(不晚于 ri)到达冰雪女王宫殿,则打印“是”(不带引号),否则打印“否”(不带引号)。

示例

输入 #1

5 4 6
1 2
2 3
3 4
3 5
1 3 1 4
1 3 2 4
1 4 4 5
1 4 4 1
2 3 1 4
2 2 2 3

输出 #1

Yes
Yes
Yes
No
No
Yes