Descrição
Você está preso em um castelo com N salas e M corredores. As salas são enumeradas com números entre 1 e N, e você inicialmente está na sala de número 1. Cada um dos M corredores liga duas salas distintas. Para tentar encontrar a saída você decidiu visitar todas as salas deste castelo.
Todas estas salas, com exceção da sala de número 1 onde você está, precisam de uma chave para que possam ser visitadas. Para sua sorte, você encontrou algumas anotações no chão, dizendo onde estão todas estas chaves. Por exemplo, sejam S e D duas salas distintas do castelo, para visitar a sala D é preciso antes visitar a sala S que contém a chave que abre a sala D.
Dadas as informacões sobre as salas, corredores e as posições das chaves, descubra se é possível visitar todas as salas do castelo.
Entrada
Haverá no máximo 70 casos de teste. Cada caso de teste inicia com dois inteiros N e M, indicando o número de salas e corredores do castelo (2 ≤ N ≤ 10^3, 1 ≤ M ≤ 10^4).
Em seguida haverá M linhas contendo dois inteiros A e B cada, indicando que há um corredor que liga a sala A e B, o qual pode ser atravessado em ambas as direções (1 ≤ A, B ≤ N).
Em seguida haverá N-1 inteiros k2, k3, …, kN, indicando que na sala ki você pode encontrar a chave que abre a sala i (1 ≤ ki ≤ N, para todo 2 ≤ i ≤ N). Note que não é dada a sala que contém a chave da sala 1, pois tal sala já está aberta.
A entrada termina com final de arquivo (EOF).
Saída
Se for possível visitar todas as salas deste castelo imprima a palavra “sim”, caso contrário imprima a palavra “nao”.
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
4 3 |
sim |