Sorvete
Por 
Brasil
Por Brasil
Joãozinho é um menino que costuma ir à praia todos os finais de semana com seus pais. Eles frequentam 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.
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.
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 (0 ≤ P ≤ 10000) e S (0 ≤ S ≤ 5000), 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.
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 Entrada | Exemplo de Saída |
|
200 2 0 21 110 180 1000 3 10 400 80 200 400 1000 10 2 1 4 5 6 0 0 |
Teste 1 0 21 110 180 Teste 2 10 1000 Teste 3 1 4 5 6 |