← 返回题目列表

AtCoder · arc045_b

B. 重击约会策略高桥君

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

問題文

高桥就读的学校将进行一次大清洁。在学校 有 N 个教室,每个教室 它们按顺序编号至 1 从 N ,并从左到右排列。

高桥君的学校包括高桥君。 有 M 名学生,教室中需要清扫的连续路段(称为清扫路段)为 M 件已经决定了。然而,尚未决定由谁负责这些清洁部分。 不同的学生被分配不同的清洁时段,被分配的学生必须清洁所有教室。1 一间教室可能包含在多个清洁期中。

高桥注意到他在打扫卫生的那天安排了和一个女孩的约会。我不知道如果我跳过约会会发生什么,所以我决定跳过清洁工作。 如上所述,有些教室可能会包含多个保洁期,所以我意识到,即使高桥逃职,只要其他人把所有教室都打扫干净,就不会明显看出他偷懒了。 如果有一间教室没有打扫干净,就会暴露你偷懒了。

你的工作是教高桥所有你可以跳过而不会被抓住的清洁部分。

除了高桥以外,这所学校的所有学生都很认真,所以请相信除了高桥之外没有人会偷懒。


入力

输入是按以下格式从标准输入给出的。

N M
s_1 t_1
s_2 t_2
:
s_M t_M
  • 1 行包含一个代表学校教室数量的整数。 N (1 ≦ N ≦ 300,000) 和代表学生人数的整数 给出了 M(1 ≦ M ≦ 100,000) 。
  • 继续 M 行包含 给出了M 清洁间隔。其中 在 i(1≦i≦M) 行中, 代表第i个清洁间隔的整数 给出了 s_i,t_i(1≦s_i≦t_i≦N) 。这意味着如果学生被分配到清洁部门, 所有符合s_i≦x≦t_i 的教室 表示必须清洁 x 。
  • 可能会给出多个相同的间隔。
  • 任何教室至少应有 1 保证包含在清洁间隔内。

出力

输出应发送到标准输出。

1 可以偷懒不被抓到的清洁路段数量 输出 k 。 在

继续 k 行,按升序输出清洁部分的数量,以换行符分隔,即使偷懒也不会检测到。还要在最后一行末尾添加换行符。

部分点

除了上述约束之外,如果正确答案是还满足以下约束的数据集, 30 点。

  • 任何教室 对于 i (1≦i≦N) ,包括教室在内的清洁区域最多为 2 这是一个。

入力例1

10 5
1 4
5 5
6 8
9 10
5 6

出力例1

2
2
5

高桥君 如果你被分配到第 2,5 个清洁工段,你偷懒就不会被抓到。具体来说, 即使分配了第

  • 2 个清洁部分,5 清洁工段是教室 无法检测到它,因为它包含 5 。 包含
  • 5 个清洁部分,2 清洁工段是教室 无法检测到它,因为它包含 5 和 3 清洁工段是教室 无法检测到它,因为它包含 6 。 包含

另一方面,高桥君, 如果你被分配到第1,3,4 个清洁工段,你偷懒就会被发现。具体来说, 如果分配了第

  • 1 个清洁区域,则教室 1,2,3,4 。
  • 3 个清洁区域,则教室 7,8 。
  • 4 个清洁区域,则教室 9,10 。

入力例2

3 6
1 1
1 1
2 2
2 2
3 3
3 3

出力例2

6
1
2
3
4
5
6

您可以跳过您选择的任何清洁部分。


入力例3

10 3
1 4
2 6
6 10

出力例3

0

高桥可能没有可以跳过的清洁部分。