問題文
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
作者:田村和典 测试员:花田佑一郎