URI Online Judge | 3069

Sorvete

Por BR Brasil

Timelimit: 1

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.

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 (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 ≤ UP e 0 ≤ VP). O final da entrada é indicado por S=0 e P=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 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