Super-plane

Problem code: SUPERPLN

All submissions for this problem are available.

Dunno was invited by Roly-Poly to his birthday party. But he don't know how to get to Roly-Poly. So Dunno turned for advice to Doono. Doono reminded him that their country of shorties have a network of super-planes airlines, which can move not only in space but also in time. Thanks to a super engine, developed by Doono and constructed by Bendum and Twistum, such aircraft, flying from one city could get to the other even before they departed.

Dunno rejoiced and rushed into the super-airport. Not thinking through his route, Dunno began to fly at super-planes aimlessly, i.e. boarded the next flight out of that city, where he was. Dunno flies until he reaches the city where Roly-Poly lives not later than the start time of the birthday party, or until it reaches a certain city, where no longer be able to fly away. The closest flight is a flight in the same city, for which the departure time is not less than the arrival time of Dunno in this city, and the difference between these time points is minimal.

Write a program, that determines whether Dunno ever gets to Roly-Poly given the schedule of the super-plane flights. If he gets the party in time then find also the number of flights he uses.

Input

The first line contains a single positive integer T <= 10, the number of test cases. T test cases follow. The first line of each test case contains the number of available flights N (0 <= N <= 10000) . Each of the following N lines contains 4 space-separated integers C1, T1, C2, T2, where C1 is the departure city, T1 is departure time, C2 is the destination city, T2 is arrival time. It is guaranteed that there are no flights with the same departure city and time. The last line of each test case contains the city where Dunno lives, the time when he came to the super-airport, the city where Roly-Poly lives and the time when the birthday party starts. All city numbers are positive integers not greater than 10000 and all time points are not greater than 100000 in absolute value.

Output

For each test case, output a single line containing the word "Yes" followed by space and the number of flights that the Dunno uses if he gets the Roly-Poly birthday party in time and "No" otherwise.

Example

Input:
3
3
1 3 4 3
4 4 3 5
3 10 2 -1
1 2 2 0
1
1 2 3 0
1 2 2 2
2
2 0 2 0
2 1 4 0
2 0 4 0

Output:
Yes 3
No
No

Author: anton_lunyov
Date Added: 14-06-2011
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

how time can be -1 ?

theeporithirumugam @ 19 Jun 2011 09:50 PM
how time can be -1 ?

I don know what u are asking

theeporithirumugam @ 19 Jun 2011 09:51 PM
I don know what u are asking us to solve ?

Do I need to output minimal

simpleton @ 19 Jun 2011 09:54 PM
Do I need to output minimal number of flights?

can u pls explain why its not

siddharth_l @ 19 Jun 2011 09:55 PM
can u pls explain why its not possible in third case?There is a flight from city 2 to city 4 and it DOES reach in time...then why should the output read no?

@theeporithirumugam, See the

rajiv_adm @ 19 Jun 2011 09:59 PM
@theeporithirumugam, See the problem statement Thanks to a super engine, developed by Doono and constructed by Bendum and Twistum, such aircraft, flying from one city could get to the other even before they departed. Also see in Input all time points are not greater than 100000 in absolute value.

Because Dunno uses the

anton_adm @ 19 Jun 2011 10:00 PM
Because Dunno uses the closest flight. In third test case closest flight is 2 0 2 0. So he will use this flight and then again this flight and so on forever.

@simpleton and @siddharth_l

rajiv_adm @ 19 Jun 2011 10:03 PM
@simpleton and @siddharth_l . See Dunno began to fly at super-planes aimlessly, i.e. boarded the next flight out of that city, where he was. For 3rd case, he cannot reach because the earliest available flight is 1. He will always take flight 1. If he would have taken flight 2, the answer would have been yes. But As per problem statement he never get a chance to board flight 2

3 1 3 4 3 4 4 3 5 3 10 2 -1 1

simpleton @ 19 Jun 2011 10:07 PM
3 1 3 4 3 4 4 3 5 3 10 2 -1 1 2 2 0 For this input, why is the arrival time for the 3rd line -1??

Time can be negative in this

anton_adm @ 19 Jun 2011 10:11 PM
Time can be negative in this problem.

If he reaches roly poly once

calc_saransh @ 19 Jun 2011 10:11 PM
If he reaches roly poly once after starttime of birthday.. and then he takes a flight from there and reaches there before then should we output no or yes??

@simpleton, Arrival time is

rajiv_adm @ 19 Jun 2011 10:12 PM
@simpleton, Arrival time is -1. As per problem statement, Arrival time can be before departure time

What if Dunno reaches the

anector @ 19 Jun 2011 10:16 PM
What if Dunno reaches the birthday airport but after the party started? Would he be upset to continue his journey and stop trying to reach in time or should he fly next flight??

Plz Expalain the Input

Najmuzzaman @ 19 Jun 2011 10:20 PM
Plz Expalain the Input

@nector. He should continue

rajiv_adm @ 19 Jun 2011 10:21 PM
@nector. He should continue his journey and take next flight

@calc_saransh, the answer

rajiv_adm @ 19 Jun 2011 10:22 PM
@calc_saransh, the answer should be yes

for any C1, can we get same

sazzad @ 19 Jun 2011 10:24 PM
for any C1, can we get same T1 more than once?

@anector: he will fly take

bminus @ 19 Jun 2011 10:25 PM
@anector: he will fly take the next flight

@sazzad, It is guaranteed

rajiv_adm @ 19 Jun 2011 10:26 PM
@sazzad, It is guaranteed that there are no flights with the same departure city and time.

The closest flight is a

theeporithirumugam @ 19 Jun 2011 10:28 PM
The closest flight is a flight in the same city, for which the departure time is not less than the arrival time of Dunno in this city, and the difference between these time points is minimal. There may be more than one closer flights ?

@theeporithirumugam No. The

anton_adm @ 19 Jun 2011 10:30 PM
@theeporithirumugam No. The closest flight is unique.

constraints on C1 and C2, are

thechamp @ 19 Jun 2011 10:35 PM
constraints on C1 and C2, are they always less than equal to N?

If Dunno and Roly-Poly live

cjoa @ 19 Jun 2011 10:41 PM
If Dunno and Roly-Poly live in the same city, must Dunno take at least one flight?

C, C2 can be greater than N

rajiv_adm @ 19 Jun 2011 10:43 PM
C, C2 can be greater than N but less than or equal to 10000

yes, the answer can be zero

rajiv_adm @ 19 Jun 2011 10:44 PM
yes, the answer can be zero flight

Explain 3rd test case.

jagadish121288 @ 19 Jun 2011 10:44 PM
Explain 3rd test case.

3rd case is already explained

rajiv_adm @ 19 Jun 2011 10:55 PM
3rd case is already explained by anton above. Because Dunno uses the closest flight. In third test case closest flight is 2 0 2 0. So he will use this flight and then again this flight and so on forever.

are city numbers positive?

riadwaw @ 19 Jun 2011 11:25 PM
are city numbers positive?

It is not actually, sorry

riadwaw @ 19 Jun 2011 11:36 PM
It is not actually, sorry

All city numbers are positive

rajiv_adm @ 19 Jun 2011 11:44 PM
All city numbers are positive integers not greater than 10000

This problem drives me

hacker007 @ 20 Jun 2011 12:17 AM
This problem drives me crazy(got a dozen of WAs). Admins, please release the test data like TopCoder/Codeforces do, so that every solution can be viewed including the wrong ones failed by which test case.

Here is my latest WA

hacker007 @ 20 Jun 2011 12:30 AM
Here is my latest WA solution(http://www.codechef.com/viewsolution/579555), anyone can give me a case that fails the code? Thanks.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions