#P2620. Minimal coverage

Minimal coverage

给定一组端点坐标为整数的线段[Li,Ri][L_i, R_i],你的任务是找到能完全覆盖线段[0,M][0, M]最小子集MM为正整数)。

Input

  • 输入第一行包含整数MM1M50001 \le M \le 5000)。
  • 后续每行包含两个整数LiL_iRiR_iLi,Ri50000|L_i|, |R_i| \le 50000),每对整数独占一行,数值间用空格分隔。
  • 输入以一对"0 0"结束。
  • 总线段数i100000i \le 100000

Output

  • 若存在解:
    1. 第一行输出最小子集的大小。
    2. 后续按左端点LiL_i升序输出子集中的所有线段,格式与输入相同(不包含结尾的"0 0")。
  • 若无解,直接输出'No solution'。

输入样例 1

1  
-1 0  
-5 -3  
2 5  
0 0  

输出样例 1

No solution  

输入样例 2

1  
-1 0  
0 1  
0 0  

输出样例 2

1  
0 1  

提示

  • 输入数据规模较大,建议使用scanf读取。

来源
1998年乌拉尔大学生程序设计竞赛