Buracos de Minhoca
Retirada de Spoj
Os chamados buracos de minhoca (em inglês, worm holes) são ligações entre dois pontos do espaço que permitem que um corpo desloque-se de um ponto ao outro instantamente. Embora atualmente sejam apenas parte de uma teoria, acredita-se que no futuro viajaremos através do espaço rapidamente utilizando buracos de minhoca.
O principal problema tecnológico a ser resolvido na construção de um buraco de minhoca é a enorme quantidade de energia envolvida. Uma dificuldade adicional é́ que buracos de minhoca são unidirecionais. Ou seja, um buraco que leve do ponto A ao ponto B não pode ser utilizado para ir do ponto B ao ponto A.
A Unicomp tem um projeto de pesquisa com o objetivo de investigar o uso de buracos de minhoca para o transporte de passageiros. O grupo de pesquisa projetou um mapa de buracos de minhoca interligando os planetas de nossa galáxia.
Tarefa
Escreva um programa que, dado um mapa de buracos de minhoca interligando os planetas, determine se é possível, a partir de qualquer um dos planetas, viajar, através de buracos de minhoca, até qualquer outro planeta.
Entrada
A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém dois números inteiros 
e 
, representando respectivamente o número de planetas 
e o número de buracos de minhocas do mapa 
. Os planetas são identificados por números de 
a . Cada uma das linhas seguintes conté́m dois inteiros 
e 
, separados por espaço em branco, representando a existência de um buraco de minhoca que permite ir do planeta para o planeta 
e != 
. O final da entrada é indicado por 
.
Saída
Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato ‘Teste n’, onde n é numerado sequencialmente a partir de . A segunda linha deve conter uma unica letra: ‘
’ se é possível viajar de qualquer planeta para qualquer outro planeta, ou ‘
’ caso contrário. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.
Exemplos
| ENTRADA | SAÍDA |
3 4 1 2 3 2 1 3 2 3 3 4 2 3 3 2 1 2 3 1 0 0 |
Teste 1 N Teste 2 S |