ESJAIL - Escape from Jail

Harry is currently a prisoner of the International Common Prison for Criminals (ICPC), the most secure prison in the world. It was designed by and old gamer and as such, the prison is not necessarily closed, but only an incredibly logical and fast mind can get out.

The prison is made of N chambers connected by M corridors. Each corridor connects exactly two chambers and can be traversed in any direction. Each chamber is either empty, contains a single unbreakable door, or contains a single key. No chamber contains both a door and a key. There are K doors and K keys in the whole prison. Each key opens a different door, and each door is opened by a different key. If a chamber contains a door, the corresponding key is needed to enter the chamber, regardless of which corridor was used to reach it.

Harry found the complete map of the prison, including the location of each door and each key, and wants to know how to get out that hell hole. According to the map, Harry is now in chamber number 1, and the exit is in chamber N . Given the information on the map, let Harry know if it is possible to escape or if he is doomed forever.

Input

The input contains several test cases, each one described in several lines. The first line of each test case contains three integers N , K, and M separated by single spaces. The value N is the number of chambers in the prison (4 ≤ N ≤ 105 ); each chamber is identified by an integer number between 1 and N . The value K is the number of doors and keys (1 ≤ K ≤ N/2), while M is the number of corridors (1 ≤ M ≤ 105). Each of the next K lines describes a door and its corresponding key using two integers A and B separated by a single space, with the following meaning: chamber A contains the key that opens the door in chamber B (2 ≤ A, B ≤ N − 1). The last M lines of the test case describe the corridors. Each of these lines contains two integers C and D separated by a single space, indicating that there is a corridor connecting chambers C and D (1 ≤ C < D ≤ N ).

You may assume that no two corridors connect the same pair of chambers. The last line of the input contains the number −1 three times separated by single spaces and should not be processed as a test case.

Output

For each test case output a single line with an uppercase “Y” if it is possible for Harry to escape from the prison, or an uppercase “N” otherwise.

Example

Input:
4 1 4
2 3
3 4
2 3
1 3
2 4
6 2 5
5 4
3 2
2 6
2 5
1 4
1 5
3 4
4 1 1
3 2
2 3
-1 -1 -1

Output:
N
Y
N

Added by:Pablo Ariel Heiber
Date:2010-08-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2008

hide comments
2022-08-08 05:44:07
common prison yet most secure one... smh.
2021-04-08 23:19:09
Did it using DFS! :)
2017-07-18 21:09:38
Compilation Error in CPP14 ..Same code AC in c++ 4.3.2.. WTF
2017-01-06 16:06:51
CAUTION:::HINTS BELOW
There are two cases
case 1: we reach a door but we dont have the key . in this case we cannot push this node in queue. we visit the key required later for this node . That is the time when we push this particular door in queue.
case 2: we reach a door and we already reached the key . we simply push the door in queue.
Dont try this with dfs .

Last edit: 2017-01-06 16:09:54
2016-09-10 22:00:39
can any one pls explain me example test case

Last edit: 2016-09-10 22:01:02
2016-03-14 12:37:37 Abhilash
Do not PUSH open the doors !!!
2014-10-06 05:11:28 Santiago Vanegas
Maybe the following could be a tricky case:
4 1 2
2 3
1 2
3 4
The answer is N
2014-09-21 07:58:35 Sachin Malhotra
What should be the answer if we reach the vertex N but it is locked and there is no way to unlock it.

3 1 1
2 3
1 3

My AC solution gives answer as Y.
2014-08-14 15:32:44 mohsin mohammad
Its BFS....my 100th...!!!!!
2014-06-18 16:34:16 Rishav Goyal
sensitive bfs :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.