Locked in the Castle
By Cristhian Bonilha, UTFPR 
Brazil
By Cristhian Bonilha, UTFPR Brazil
You are locked inside a castle with N rooms and M corridors. The rooms are numbered with numbers between 1 and N, and you are initially at the room number 1. Each of the M corridors connects two distinct rooms. To try to leave you decided to visit all of the N rooms of the castle.
All of the rooms, with exception of the room number 1 where you are, need a key to be visited. You had luck to find some notes in the ground, saying where all of these keys are. For exemple, be S and D two distinct rooms, to visit the room D you need to first visit the room S that has the key to open the room S.
Given the information about the rooms, corridors and the key locations, find out if it's possible to visit all of the rooms of the castle.
There will be at most 70 test cases. Each test case starts with two integers N and M, indicating the number of rooms and corridors of the castle (2 ≤ N ≤ 103, 1 ≤ M ≤ 104).
Following there will be M lines containing two integers A and B each, indicating that there's a corridor that connects the room A and B, which can be traversed in both directions (1 ≤ A, B ≤ N).
Following there will be N-1 integers k2, k3, …, kN, indicating that in the room ki you can find the key to open the room i (1 ≤ ki ≤ N, for all 2 ≤ i ≤ N). Note that there's no room that contains the key to the room number 1, because this is the first room you are in and it's open.
The input ends with end of file (EOF).
If it's possible to visit all of the rooms of the castle print the word “sim”, otherwise print the word “nao”.
| Input Sample | Output Sample |
|
4 3 |
sim |