Module: Método de linha de varredura

Um certo conjunto de segmentos com coordenadas inteiras de extremidades \([L_i, R_i]\) é dado em uma linha. Entre o conjunto fornecido, escolha um subconjunto de segmentos que cubra completamente o segmento \([0, M]\), (M — número natural) contendo o menor número de segmentos.

 

A primeira linha contém a constante M (\(1<=M<=5000\)). Cada linha subsequente contém um par de números Li e Ri (\(|L_i|,|R_i| < 50000\)), que especifica as coordenadas das extremidades esquerda e direita dos segmentos. A lista termina com um par de zeros. O número total de segmentos não excede 100.000.

 

Na primeira linha do arquivo de saída, imprima o número mínimo de segmentos necessários para cobrir o segmento \([0; M]\). Em seguida, imprima uma lista do subconjunto de cobertura, classificado em ordem crescente pelas coordenadas das extremidades esquerdas dos segmentos. A lista de segmentos é gerada no mesmo formato da entrada. Os dois zeros à direita não são necessários. Se o segmento \([0; M]\) for o conjunto original de segmentos \([L_i, R_i] \)< /span> não for possível, uma única frase “Sem solução” deve ser gerada.

 

Exemplos

#	Entrada	Saída
1	1 -1 0 -5 -3 2 5 0 0	Sem solução
2	1 -1 0 0 1 0 0	1 0 1