← 返回题目列表

AtCoder · kupc2012_4

D. 电源

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

問題文

10号楼是某大学的大楼,是J研究生院的成员日夜进行研究的设施。

10号楼因老建筑而闻名,但今年终于翻新了。 有一天,当大家都希望改造完成后能够在一个干净的环境中进行研究时, 我们收到消息称,10号楼装修工程完成后,K研究生院的部分人员将侵入该房间。

如果10号楼的房间被K研究生院入侵,在该房间工作的J研究生院的成员将不得不搬到2号楼,这也是一栋较旧的建筑。 既然必须采取行动阻止,J研究生院的教授们决定集中力量,保护10号楼的每个房间免受K研究生院的侵害。

10号楼是 N 房间排成一条直线,并且按顺序排列 它的编号为 1,2,...,N 。 K大学院是这个 N 将尝试入侵所有房间。 在J研究生院 M 教授有多名,每个教授可以对某个科室所包含的房间行使权力。 K研究生院可以保护有一名或多名教授行使权力的房间不被入侵,但没有教授行使权力的房间就会被入侵。

教授忙于研究,所以我想用尽可能少的人来保护所有房间。 找出应行使权力保护所有房间的最少教授人数。 请注意,即使所有教授都行使职权,也可能无法保护所有房间。

入力形式

输入按以下格式给出。

N\ M\\
a1\ b1\\
...\\
aM\ bM

N 是 10 号楼的房间数,M 是 J 研究生院的教授人数。

ai, bi 是,教授 i 是房间 这意味着能够对 ai, ai+1, ..., bi 行使权力。

出力形式

如果可以保护 10 号楼的所有房间,请打印一行中应行使权力的教授的最少人数。 否则 在一行上输出Impossible 。

制約

  • 1 ≤ N ≤ 100, 1 ≤ M ≤ 100
  • 1 ≤ ai ≤ bi ≤ N
  • 所有输入值都是整数。

入出力例

入力例 1

8 4
3 7
1 5
2 5
4 8

出力例 1

2

2 与教授 通过发挥他的力量,第 4 教授可以保护10号楼的所有房间。

入力例 2

8 4
1 4
2 5
3 6
4 7

出力例 2

Impossible

作者:田村和典
测试员:花田佑一郎