SPOJ Brasil

Uma empresa possui vários computadores conectados em rede. Isto possibilita que os funcionários compartilhem recursos e consigam colaborar melhor para o desempenho de suas tarefas dentro da empresa. No entanto, as máquinas não estão diretamente conectadas todas entre si. Por economia de recursos, a topologia de rede adotada apresenta apenas um subconjunto das conexões possíveis, conforme o exemplo apresentado na figura abaixo. Note que as conexões são sempre bidirecionais.

1 -- 2    6
|    |    |
|    |    |
3 -- 4 -- 5

Apesar de alguns computadores não estarem diretamente conectados entre si, eles ainda conseguem se comunicar porque existe um algoritmo de roteamento capaz de conectar dois computadores através de várias conexões diretas. No exemplo da figura, o computador 1 conseguiria se comunicar com o computador 5 através dos computadores 2 e 4 ou através dos computadores 3 e 4.

No entanto, freqüentemente as máquinas precisam passar por uma revisão de rotina. Quando uma máquina está em manutenção, ela precisa ser temporariamente desconectada da rede e levada para a oficina. Assim, o algoritmo de roteamento não tem mais como estabelecer conexões utilizando este computador, o que pode acabar desconectando duas ou mais partes da rede e prejudicando o trabalho na empresa. No exemplo dado, se o computador 2 fosse para a revisão não teríamos problema pois todas as outras máquinas ainda conseguiriam se comunicar entre si. No entanto, se o computador 4 fosse para a manutenção, as máquinas 1, 2 e 3 não conseguiriam se comunicar com as máquinas 5 e 6.

Se a remoção de uma máquina desconectar o restante da rede, impedindo que outros computadores se comuniquem, é necessário deixar uma máquina substituta em seu lugar durante o período de manutenção, o que representa um custo extra no orçamento da empresa.

Tarefa

Sua tarefa é escrever um programa que identifique quais são os computadores que precisam ser substituídos durante a sua manutenção, para que os demais continuem se comunicando através da rede.

Entrada

A entrada é constituída de vários conjuntos de teste. A primeira linha de um conjunto de teste contém dois números inteiros N e M, que indicam respectivamente o número de computadores na rede e o número de conexões diretas entre eles (1 <= N <= 400, e N-1 <= M <= N(N-1)/2). Os computadores são identificados por números de 1 a N. As M linhas seguintes contêm, cada uma, um par de números inteiros X e Y. Cada linha representa uma conexão existente na rede, indicando que os computadores X e Y possuem uma conexão direta entre si. O final da entrada é indicado por um conjunto de teste com N = M = 0. Você pode assumir que todos os conjuntos de teste representam redes conexas, onde todos os computadores conseguem se comunicar entre si através do algoritmo de roteamento.

Exemplo de Entrada
6 6
1 2
3 1
2 4
3 4
4 5
5 6
4 6
1 2
1 3
1 4
2 3
2 4
3 4
4 3
1 2
1 3
1 4
0 0

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 a partir de 1. A segunda linha deve conter a lista com os computadores que precisam ser substituídos durante sua manutenção. Esta lista deve estar ordenada de forma crescente, e cada valor deve ser seguido de um espaço em branco. Caso nenhum dos computadores da rede precise ser substituído, escreva "nenhum" na saída. A terceira linha deve ser deixada em branco. O formato mostrado no exemplo de saída abaixo deve ser seguido rigorosamente.

Exemplo de Saída
Teste 1
4 5

Teste 2
nenhum

Teste 3
1

(esta saída corresponde ao exemplo de entrada acima)

Restrições

0 <= N <= 400 (N = 0 apenas para indicar o fim da entrada)
N - 1 <= M <= N(N - 1)/2
1 <= X <= N
1 <= Y <= N
X != Y