Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SORVETE - Sorvete

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


Adicionado por:Wanderley Guimarăes
Data:2007-02-24
Tempo limite:0.116s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Olimpiada Brasileira de Informatica 2001

hide comments
2016-04-06 06:35:58 Elsio [UFABC]
Semelhante ao JDENTIST do spoj
2014-05-20 23:04:14 Avic
Pequeno cuidado a mais porque as restriçőes dadas năo săo respeitadas. O certo é 0 ≤ U ≤ V ≤ P. U=V acontece na execuçăo.
2012-10-02 23:01:10 [deleted]
No exemplo, U1 <= U2 <= U3... <= US
Pode-se considerar que a entrada está sempre organizada desta forma? [2]
2011-09-09 00:04:33 thiagojobson [UERN]
Como se fosse
( ( ) () )
10 80 200 400 1000
2011-07-29 19:35:41 Vinicius [CCCLAN-UGF]
Considerem um intervalo 1 - 4 e outro intervalo 4 - 6. Ambos intervalos devem ser consideramos como um só (1 - 6) ou como 2 intervalos separados?
2011-07-28 06:27:24 Fernando Lucchesi
O problema diz que U<V, mas eu tive que considerar U<=V para ser aceito.
(se bem que o bug do meu programa pode estar em outro lugar)
2011-03-04 20:28:07 Kelvin Azevedo Santos [FMUSP]
No exemplo, U1 <= U2 <= U3... <= US
Pode-se considerar que a entrada está sempre organizada desta forma?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.