Minimum Coverage#4426
Given a set of line segments with integer coordinates for their endpoints L_i, R_i, your task is to select the smallest subset of these segments that completely covers the segment , where is a positive integer.
The first line contains an integer (1 \leq M \leq 5000). Each of the following lines contains a pair of integers L_i and R_i (|L_i|, |R_i| \leq 50000), with each pair on a new line and numbers separated by one or more spaces. The input ends with a pair of zeros. There are no more than pairs of numbers, including the terminating pair of zeros.
The output should start with the minimum number of segments required to cover the segment . This should be followed by the list of segments in the covering subset, ordered by the increasing coordinates of their left endpoints. The format of the list should match the input format, excluding the terminating pair of zeros.
If it is not possible to cover the segment with the provided segments [L_i, R_i], the output should be the single phrase No solution.
Example 1