International Corporation for Protection and Control (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$ กล้องจะครอบคลุมทุกผนัง $j$ ที่ $a_i \le j \le b_i$ ถ้า $a_i > b_i$ กล้องจะครอบคลุมทุกผนัง $j$ ที่ $a_i \le j \le n$ หรือ $1 \le j \le b_i$

ข้อมูลส่งออก

แสดงจำนวนกล้องน้อยที่สุดที่เพียงพอจะครอบคลุมผนังทุกด้านของอาคาร ช่วงที่กล้องสองตัวครอบคลุมสามารถซ้อนทับกันได้ หากไม่สามารถครอบคลุมทั้งอาคารได้ ให้แสดง 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