SPOJ Brasil

Como prêmio pela primeira colocação na Olimpíada Brasileira de Informática, Juquinha e sua família ganharam uma viagem de uma semana à Coréia do Sul. Como o país é deslumbrante, com tradições, cultura, arquitetura e culinária muito diferentes das do Brasil, o pai de Juquinha, o Sr. Juca, decidiu alugar um carro para conhecer melhor o país. As estradas são muito bem cuidadas; todas são de sentido duplo, e duas cidades podem ser ligadas diretamente por mais de uma estrada. No entanto, em todas as estradas paga-se um pedágio de valor fixo (há um pedágio em cada direção, entre duas cidades). Como o Sr. Juca não tem muito dinheiro para gastar, as viagens com o carro devem ser muito bem planejadas.

Tarefa

Escreva um programa que, conhecidas as cidades e estradas existentes no país, e a cidade onde Juquinha e sua família estão, encontre cada cidade (que não a cidade onde eles estão) que possa ser visitada por eles, dada a restrição de que o Sr. Juca deseja pagar no máximo P pedágios (considerando apenas a viagem de ida).

Entrada

A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém quatro números inteiros C, E, L e P. Os valores C e E indicam respectivamente o número de cidades e o número de estradas existentes. As cidades são identificadas por inteiros de 1 a C. os valores L e P indicam, respectivamente, a cidade onde a família de Juquinha está no momento e o número máximo de pedágios que o Sr. Juca está disposto a pagar. As E linhas seguintes contêm cada uma a informação de uma estrada, representada por um par de números inteiros positivos X e Y, indicando que há uma estrada (de sentido duplo) da cidade X para a cidade Y. O final da entrada é indicado por C = E = L = P = 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. Na segunda linha devem aparecer os identificadores das cidades que podem ser alcançadas, em ordem crescente, separados por pelo menos um espaço em branco. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo

Entrada:
5 4 2 1
1 2
2 3
3 4
4 5
9 12 1 2
2 1
1 5
2 1
3 2
9 3
3 4
4 8
4 7
7 6
5 6
4 5
3 7
0 0 0 0

Output:
Teste 1
1 3

Teste 2
2 3 4 5 6

Restrições

0 <= C <= 50 (C = 0 apenas para indicar o fim da entrada)
0 <= E <= 2500 (E = 0 apenas para indicar o fim da entrada)
0 <= L <= C (L = 0 apenas para indicar o fim da entrada)
0 <= P <= C (P = 0 apenas para indicar o fim da entrada)
1 <= X <= C
1 <= Y <= C