CF685E.Travelling Through the Snow Queen's Kingdom

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Gerda is travelling to the palace of the Snow Queen.

The road network consists of nn intersections and mm bidirectional roads. Roads are numbered from 11 to mm . Snow Queen put a powerful spell on the roads to change the weather conditions there. Now, if Gerda steps on the road ii at the moment of time less or equal to ii , she will leave the road exactly at the moment ii . In case she steps on the road ii at the moment of time greater than ii , she stays there forever.

Gerda starts at the moment of time ll at the intersection number ss and goes to the palace of the Snow Queen, located at the intersection number tt . Moreover, she has to be there at the moment rr (or earlier), before the arrival of the Queen.

Given the description of the road network, determine for qq queries lil_{i} , rir_{i} , sis_{i} and tit_{i} if it's possible for Gerda to get to the palace on time.

输入格式

The first line of the input contains integers nn , mm and qq ( 2<=n<=10002<=n<=1000 , 1<=m,q<=2000001<=m,q<=200000 ) — the number of intersections in the road network of Snow Queen's Kingdom, the number of roads and the number of queries you have to answer.

The ii -th of the following mm lines contains the description of the road number ii . The description consists of two integers viv_{i} and uiu_{i} ( 1<=vi,ui<=n1<=v_{i},u_{i}<=n , viuiv_{i}≠u_{i} ) — the indices of the intersections connected by the ii -th road. It's possible to get both from viv_{i} to uiu_{i} and from uiu_{i} to viv_{i} using only this road. Each pair of intersection may appear several times, meaning there are several roads connecting this pair.

Last qq lines contain the queries descriptions. Each of them consists of four integers lil_{i} , rir_{i} , sis_{i} and tit_{i} ( 1<=li<=ri<=m1<=l_{i}<=r_{i}<=m , 1<=si,ti<=n1<=s_{i},t_{i}<=n , sitis_{i}≠t_{i} ) — the moment of time Gerda starts her journey, the last moment of time she is allowed to arrive to the palace, the index of the starting intersection and the index of the intersection where palace is located.

输出格式

For each query print "Yes" (without quotes) if Gerda can be at the Snow Queen palace on time (not later than rir_{i} ) or "No" (without quotes) otherwise.

输入输出样例

  • 输入#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
    
首页