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 necesarilly 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 ≤ 10^{5} ); 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 ≤ 10^{5} ). 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 cointains 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 cointains 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
hide comments
sas1905:
20170718 21:09:38
Compilation Error in CPP14 ..Same code AC in c++ 4.3.2.. WTF 

conquistador:
20170106 16:06:51
CAUTION:::HINTS BELOW


blackjack123:
20160910 22:00:39
can any one pls explain me example test case Last edit: 20160910 22:01:02 

Abhilash:
20160314 12:37:37
Do not PUSH open the doors !!! 

Santiago Vanegas:
20141006 05:11:28
Maybe the following could be a tricky case:


Sachin Malhotra:
20140921 07:58:35
What should be the answer if we reach the vertex N but it is locked and there is no way to unlock it.


mohsin mohammad:
20140814 15:32:44
Its BFS....my 100th...!!!!! 

Rishav Goyal:
20140618 16:34:16
sensitive bfs :) 

Aditya Gourav:
20130326 17:36:46
I can't believe I did it in first attempt!! 

张翼德:
20121216 11:12:57
submission id  8258164... am getting SIGKILL here on spoj, but its taking only 37MB on ideone :/ Its difficult to code in C# with such barriers _ Last edit: 20121216 11:13:28 
Added by:  Pablo Ariel Heiber 
Date:  20100819 
Time limit:  0.968s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 VB.NET 
Resource:  FCEyN UBA ICPC Selection 2008 