问题 4855 --一锐在固定

4855: 一锐在固定★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 24  解决: 19
[提交][状态][命题人:]

题目描述

在x轴上有 n个片段。

一锐可以在x轴的任意整数点的坐标上钉上钉子,

这样,所有包含此整数点的片段都被钉上了。

注意,如果钉子在某片段的端点,也认为这一片段被钉上。

请问把给定的所有片段钉上所需的钉子数的最小值为多少?

输入

第一行为整数n(1=<n<=1000),为片段的数量。

接下来n行,每行为两个数,即片段的两个端点的坐标值。

所有坐标值的绝对值不超过10000.

注:片段可以是一个点。

输出

第一行输出一个整数:把所有片段钉上所需的钉子数的最小值。第二行输出所有钉子所在位置的坐标值,每两个坐标值之间空一格。

如果答案不唯一,输出其中之一即可。

样例输入
Copy
2
0 2
2 5
样例输出
Copy
1
2 

提示

样例2输入

5
0 3
4 2
4 8
8 10
7 7

样例2输出

3
7 10 3

来源

[提交][状态]