#6561. 小奇的旅行计划

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: hzwer

题目描述

小奇所在的国家一共由 n 个城市和 m 条连接这些城市的双向道路组成。

小奇非常喜欢骑自行车,它常常骑着自行车从一个城市,沿着某些双向道路到达另一个城市。

现在,这个国家要关闭其所有的道路以便翻修,但为了保证必要的交通运输,第 i 条道路会在第 i 天暂时开放。

小奇为了了解本次翻修对它旅行的影响,因此想知道,如果它第 l 天在一个城市 s ,在第 r 天或之前是否能到达城市 t
(小奇不需要第 l 天就立即离开 s ,也不需要恰好在第 r 天到达城市 t 。)

为了更全面地评估这个影响,小奇会有许多的询问,但它一下子算不过来,就只好找你帮忙了。

输入格式

第一行三个正整数 n,m,q ,分别表示城市数、道路数、询问数。

接下来有 m 行,其中第 i 行有两个正整数 u_i, v_i (u_i\neq v_i) ,表示有一条连接 u_i, v_i 两座城市的双向道路,并且这条道路在第 i 天暂时开放,不保证整张图连通,不保证有且仅有一条道路连接 u_i, v_i 两座城市。

接下来 q 行,每行四个正整数 l_i, r_i, s_i, t_i ,表示一个询问。

输出格式

q 行,第 i 行表示第 i 个询问的答案,可行输出 Yes ,不可行输出 No

样例

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

数据范围与提示

对于 30\% 的数据, m, q\leq 2000
对于所有数据均有: 2\leq n\leq 1000, 1\leq m, q\leq 200000, 1\leq l_i\leq r_i\leq m, 1\leq s_i, t_i\leq n, s_i\neq t_i
本题版权归 Trinkle23897 所有