Module: Scanline-Methode

Auf einer geraden Linie sind einige Linien mit ganzzahligen Endenkoordinaten angegeben \([L_i, R_i]\). Wählen Sie unter dieser Menge eine Teilmenge der Linien aus, die die gesamte Linie \([0, M]\), (M — eine natürliche Zahl) umfasst, die die kleinste Anzahl von Linien enthält.

 

Die erste Zeile enthält die Konstante M (\(1<=M<=5000\)). In jeder nachfolgenden Zeile sind ein Zahlenpaar Li und Ri (\(|L_i|,|R_i| < 50000\)) geschrieben, das die Koordinaten des linken und rechten Endes der Segmente angibt. Die Liste wird mit ein paar Nullen abgeschlossen. Die Gesamtzahl der Segmente überschreitet 100.000 nicht.

 

Geben Sie in der ersten Zeile der Ausgabedatei die Mindestanzahl an Segmenten aus, die zum Abdecken des Bereichs \([0; M]\) erforderlich sind. Geben Sie als Nächstes eine Liste der abdeckenden Teilmenge an, die nach den Koordinaten der linken Enden der Segmente aufsteigend angeordnet ist. Die Liste der Segmente wird im gleichen Format wie in der Eingabe angezeigt. Die letzten beiden Nullen müssen nicht ausgegeben werden. Wenn die \([0; M]\) mit dem ursprünglichen Satz von \([L_i, R_i]\) nicht möglich ist, sollte ein einzelner Ausdruck “No solution” ausgegeben werden.

 

Beispiele

№	Eingabe	Ausgabe
1	1 -1 0 -5 -3 2 5 0 0	No solution
2	1 -1 0 0 1 0 0	1 0 1