国际保护与控制公司（ICPC）开发了高效的技术，用于保护和控制。自然地，他们希望自己的总部大楼也能得到保护和控制。从上方俯瞰，总部大楼呈凸多边形形状。大楼周围有几个合适的位置可以安装摄像头来监控大楼。每个摄像头根据其位置，覆盖多边形边（大楼墙壁）的一定范围。ICPC 希望最小化覆盖整座大楼所需的摄像头数量。

输入格式

输入包含单个测试用例。第一行包含两个整数 $n$ 和 $k$（$3 \le n \le 10^6$ 且 $1 \le k \le 10^6$），其中 $n$ 是墙壁的数量，$k$ 是安装摄像头的可选位置数量。接下来的 $k$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$）。这些整数指定了第 $i$ 个位置的摄像头所覆盖的墙壁。如果 $a_i \le b_i$，则该摄像头覆盖所有满足 $a_i \le j \le b_i$ 的墙壁 $j$。如果 $a_i > b_i$，则该摄像头覆盖所有满足 $a_i \le j \le n$ 或 $1 \le j \le b_i$ 的墙壁 $j$。

输出格式

输出覆盖大楼每一面墙壁所需的最少摄像头数量。两个摄像头覆盖的范围可以重叠。如果无法覆盖整座大楼，则输出 impossible。

样例

样例输入 1

100 7
1 50
50 70
70 90
90 40
20 60
60 80
80 20

样例输出 1

3

样例输入 2

8 2
8 3
5 7

样例输出 2

impossible

样例输入 3

8 2
8 4
5 7

样例输出 3

2