Intermediário Informática - Semana 13

0 Flares Facebook 0 0 Flares ×

Preso no Castelo

 

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 ≤ 103, 1 ≤ M ≤ 104).

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 ≤ AB ≤ N).

Em seguida haverá N-1 inteiros k2k3, …, 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”.

Exemplo de Entrada Exemplo de Saída
4 3
1 2
2 3
3 4
1 2 3
4 3
1 2
2 3
3 4
3 1 2
sim
nao
0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: