SPOJ Brasil

Teobaldo trabalha para o governo brasileiro. No seu trabalho, ele costuma viajar muito. Quando Teobaldo viaja de uma cidade S para uma cidade E ele pode gastar até D dias nesta viagem.

Como Teobaldo não gosta de trabalhar, ele sempre gasta o número máximo de dias nas suas viagens. Em cada dia da viagem, Teobaldo dorme em uma cidade diferente da cidade do dia anterior, pois ele acha chato ficar na mesma cidade dois dias consecutivos.

Neste problema, você deve ajudar Teobaldo a planejar suas viagens.

Entrada

O arquivo de entrada contém vários conjuntos de teste. A descrição de cada conjunto é dada a seguir:

Cada conjunto começa com dois inteiros C (0 < C ≤ 100), o número de cidades, e L (0 ≤ L ≤ 500), o número de estradas entre as cidades. Seguem L linhas, onde cada linha possui dois números: A e B (1 ≤ A,B ≤ C), indicando que há uma estrada entre estas duas cidades. Você pode assumir que A e B são números diferentes. Depois dessas L linhas, há três inteiros: S, E e D, onde S é a cidade onde a viagem deve começar, E é a cidade onde a viagem deve terminar, e D (0 ≤ D ≤ 200) é o número máximo de dias para Teobaldo ir de S para E.

A entrada é terminada por um conjunto onde C = L = 0. Este conjunto não deve ser processado. Há uma linha em branco entre dois conjuntos de entrada.

Saída

Para cada conjunto de entrada produza uma linha de saída indicando se Teobaldo pode viajar do jeito que ele deseja. Veja os exemplos a seguir para o formato exato de entrada/saída.

Exemplo

Entrada:
3 2
1 2
2 3
3 1 2
	
3 2
1 2
1 3
1 3 2
	
0 0

Saída:
Yes, Teobaldo can travel.
No, Teobaldo can not travel.

Autor do Problema: Sérgio Queiroz de Medeiros