SPOJ Brasil

Joãozinho é um menino que costuma ir à praia todos os finais de semana com seus pais. Eles freqüentam sempre a mesma praia, mas cada semana o pai de Joãozinho estaciona o carro em um local diferente ao longo da praia, e instala sua família em um ponto na praia em frente ao carro. Joãozinho é muito comilão, e adora de tomar sorvete na praia. Contudo, alguns dias acontece de nenhum sorveteiro passar pelo local onde eles estão. Intrigado com isto, e não querendo mais ficar sem tomar seu sorvete semanal, Joãozinho foi até a Associação dos Sorveteiros da Praia (ASP), onde ficou sabendo que cada sorveteiro passa o dia percorrendo uma mesma região da praia, indo e voltando. Além disto, cada sorveteiro percorre todos os dias a mesma região. Jõaozinho conseguiu ainda a informação dos pontos de início e fim da região percorrida por cada um dos sorveteiros.

Com base nestes dados, Joãozinho quer descobrir os locais da praia onde o pai dele deve parar o carro, de forma que pelo menos um sorveteiro passe naquele local. Só que o volume de dados é muito grande, e Joãozinho está pensando se seria possível utilizar o computador para ajudá-lo nesta tarefa. No entanto Joãozinho não sabe programar, e está pedindo a sua ajuda.

Tarefa

Você deve escrever um programa que leia os dados obtidos pelo Joãozinho e imprima uma lista de intervalos da praia por onde passa pelo menos um sorveteiro.

Entrada

Seu programa deve ler vários conjuntos de teste. A primeira linha de um conjunto de teste contém dois inteiros não negativos, P e S, que indicam respectivamente o comprimento em metros da praia e o número de sorveteiros. Seguem-se S linhas, cada uma contendo dois números inteiros U e V que descrevem o intervalo de trabalho de cada um dos sorveteiros, em metros contados a partir do início da praia (U < V, 0 ≤ U ≤ P e 0 ≤ V ≤ P). O final da entrada é indicado por S = 0 e P = 0.

Exemplo de Entrada
200 2
0 21
110 180
1000 3
10 400
80 200
400 1000
10 2
1 4
5 6
0 0

Saída

Para cada conjunto de teste da entrada seu programa deve produzir uma lista dos intervalos da praia que são servidos por pelo menos um sorveteiro. A lista deve ser precedida de uma linha que identifica o conjunto de teste, no formato "Teste n", onde n é numerado a partir de 1. Cada intervalo da lista deve aparecer em uma linha separada, sendo descrito por dois números inteiros U e V, representando respectivamente o início e o final do intervalo (U <V). O final da lista de intervalos deve ser indicado por uma linha em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo de Saída
Teste 1
0 21
110 180

Teste 2
10 1000

Teste 3
1 4
5 6

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

Restrições

0 ≤ P ≤ 10000 (P = 0 apenas para indicar o final da entrada)
0 ≤ S ≤ 5000 (S = 0 apenas para indicar o final da entrada)
0 ≤ U <V ≤ P