問題文
高桥就读的学校将进行一次大清洁。在学校 有 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
高桥可能没有可以跳过的清洁部分。