Bank Robbery

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 256M

Problem type

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 1 \le S \le 10^5 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 N rooms, numbered 1 to N, with M hallways connecting them. E 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 F, does not have a door to the outside, or a security guard inside.


1 \le E, F < N \le M \le 10^5

1 \le a_i, b_i \le N

Input Specification

The first line of input will contain five integers: N, M, E, S, and F.

The second line of input will contain E integers, the rooms that have an exit to the outside.

The third line of input will contain S integers, the room where each guard is currently positioned.

The next M 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


Sample Explanation

No guard can get to room 5 before your friend does, and so your friend is able to escape.


There are no comments at the moment.