問題文
10号館とはとある大学にある建物で、J研究科のメンバーが日夜研究に勤しんでいる施設である。
10号館は建物が古いことで有名であったが、今年ついに改装されることになった。改装工事終了後は綺麗な環境で研究が出来ると皆が期待していたある日、K研究科の一部が、改装工事終了後の10号館の部屋を侵略するという知らせが届いた。
もしK研究科に10号館の部屋が侵略されれば、その部屋で活動していたJ研究科のメンバーはこれまた建物が古いことで知られる2号館に移動する必要がある。何とか阻止しなければならないので、J研究科は教授が権力を出しあって10号館の各部屋をK研究科から守ることにした。
10号館は N 個の部屋が1直線上に並んでおり、順番に 1,2,・・・,N の番号が付けられている。K研究科は、この N 個の部屋を全て侵略しようとしてくる。J研究科には M 人の教授が在籍しており、各教授はある区間に含まれる部屋に対して権力を発揮できる。 1人以上の教授に権力を発揮された部屋はK研究科に侵略されることはなく守ることが出来るが、どの教授からも権力を発揮されなかった部屋は侵略されてしまう。
教授は研究で忙しいので、出来るだけ少人数で全ての部屋を守りたい。全ての部屋を守るために権力を発揮するべき教授の最少人数を求めよ。なお、教授全員が権力を発揮しても全ての部屋を守ることが出来無い場合があることに注意せよ。
入力
N M a1 b1 … aM bM
N は10号館の部屋の数であり、M はJ研究科の教授の数である。
ai,bi は、教授 i が部屋 ai,ai+1,…,bi に対して権力を発揮することが出来る事を意味する。
出力
10号館の全ての部屋を守ることが出来るなら、そのために権力を発揮するべき教授の最少人数を1行に出力せよ。そうでなければ "Impossible" を1行に出力せよ。
制約
・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