Ambulância

O município de Águas Molhadas é formado por várias vilas interligadas por igarapés. Os igarapés funcionam como sistema viário, já que a maioria dos habitantes usa barcos como meio de transporte. Os igarapés têm uma forte corrente, o que obriga os barcos a transitarem todos no mesmo sentido em cada igarapé (na verdade, é proibido o trânsito de barcos na contra-mão). A prefeitura do município mantém um único Posto de Saúde e um barco-ambulância utilizado para transporte de doentes.

O timoneiro do barco-ambulância está sempre com pressa, e tem medo de confundir-se no emaranhado de igarapés quando atende um chamado para buscar um doente em alguma vila. Por isso, ele deseja uma lista de todos os possíveis caminhos entre a vila onde se encontra o Posto de Saúde e cada outra vila do município.

Tarefa

Sua tarefa é escrever um programa que liste todos os caminhos que partem da vila onde se encontra o Posto de Saúde até cada outra vila do município, de forma que em cada caminho nenhuma vila é repetida. As vilas são numeradas de 1 a N, sendo que a vila onde se encontra o Posto de Saúde será sempre a de número 1.

Entrada

A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém um número inteiro N que indica a quantidade de vilas do município. As linhas seguintes contêm, cada uma, dois inteiros positivos X e Y que indicam que a vila X tem um igarapé que a liga diretamente com a vila Y, sem passar por outras vilas, com o trânsito fluindo na direção de X para Y. O final da lista de igarapés é indicado por X = 0 e Y = 0. O final da entrada é indicado por N = 0.

Exemplo de Entrada

2
1 2
2 1
0 0
7
1 2
2 6
7 4
7 1
4 5
4 3
3 4
6 4
6 7
6 2
5 7
0 0
0

Saída

Para cada conjunto de teste da entrada seu programa deve produzir um conjunto de saída com uma lista de caminhos. A primeira linha de um conjunto de saída deve conter o identificador do conjunto, no formato "Teste n", onde n é numerado a partir de 1. As linhas seguintes devem conter os caminhos, ordenados lexicograficamente. Cada caminho é composto de uma seqüência de identificadores de vilas separados por um ou mais espaços em branco. A última linha de um conjunto de saída deve ser deixada em branco.

Exemplo de Saída

Teste 1
1 2

Teste 2 
1 2
1 2 6
1 2 6 4
1 2 6 4 3
1 2 6 4 5 
1 2 6 4 5 7
1 2 6 7
1 2 6 7 4
1 2 6 7 4 3
1 2 6 7 4 5

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

Restrições

0 ≤ N ≤ 100 (N = 0 apenas para indicar o final da entrada)
1 ≤ Y ≤ N
1 ≤ X ≤ N