After getting involved with a criminal organization, you and your friend have been tasked to rob one of the most secure banks in the world! So secure, in fact, that there may be anywhere from security guards roaming around the building at any given time.
However, as the bank is very big, your friend has somehow managed to find a way in. You hear on radio that they've collected the loot, but the path they came in through is blocked by a security guard. It's up to you to find a new path so you both leave the building unnoticed.
Luckily, you're right beside the security room. After drugging the guard inside, you now see an array of cameras in front of you. On the wall is a map of the entire building, and with the help of the cameras, you quickly determine where each guard is positioned.
There are rooms, numbered to , with hallways connecting them. of these rooms have an exit to the outside, which your friend can take to escape. But with so much loot, your friend can only walk, about as fast as a secuity guard. That is, for every hallway your friend crosses, every guard may also cross a hallway in that time. You're sure you can escape by making a run for it as soon as your friend has left the building, but first can you determine if it is possible for your friend to escape? More formally, reach a room with an exit without ever possibly being in the same room as a security guard.
It is guaranteed the room your friend is in right now, room , does not have a door to the outside, or a security guard inside.
Constraints
Input Specification
The first line of input will contain five integers: , , , , and .
The second line of input will contain integers, the rooms that have an exit to the outside.
The third line of input will contain integers, the room where each guard is currently positioned.
The next lines wil each contain two integers, representing a hallway between those two rooms. Note each hallway is bi-directional.
Output Specification
Output YES
if it is possible for your friend to escape, output NO
otherwise.
Sample Input
5 6 2 2 1
3 5
2 3
1 2
2 3
3 4
4 5
1 5
2 4
Sample Output
YES
Sample Explanation
No guard can get to room before your friend does, and so your friend is able to escape.
Comments