← 返回题目列表

Codeforces · 22/D

D. 段

中文机器翻译题面 查看原题

Ox 轴上有 n 段。您可以在 Ox 轴线钉子上的任何整数点上钉一个钉子,这样包含该点的所有线段都被视为钉住了。如果钉子穿过某个线段的端点,则该线段也被认为是被钉住的。将所有部分钉牢所需的最少钉子数量是多少?

输入

输入的第一行包含单个整数 n (1 ≤ n ≤ 1000) — 段数。接下来的 n 行包含段的描述。每个描述都是一对整数——端点坐标。所有坐标的绝对值不超过10000。线段可以退化为点。

输出

第一行应包含一个整数——钉住所有线段所需的最小钉子数量。第二行应包含按任意顺序以空格分隔的钉子坐标。如果答案不唯一,则输出任意一个。

示例

输入 #1

2
0 2
2 5

输出 #1

1
2

输入 #2

5
0 3
4 2
4 8
8 10
7 7

输出 #2

3
7 10 3