홍준이는 한국에서 손에 꼽히는 부자 중 한 명이다. 홍준이의 집은 N개의 방이 원형으로 나열된 형식으로 구성되어 있다. 홍준이는 자신의 집에 K개의 감시 카메라를 설치했다. 각 감시 카메라는 원형으로 나열된 방들 중 일부 연속된 구간을 감시한다. 홍준이는 모든 방을 다 감시하고 싶어 하는데, 이미 설치된 K개의 감시 카메라 중 몇 개는 필요하지 않다는 것을 깨달았다.

홍준이의 방은 1번 방부터 N번 방까지 원형으로 배열되어 있다. 즉, 1번 방 양 옆에는 2번 방과 N번 방이 있고, N번 방 양 옆에는 N-1번 방과 1번 방이 있다.

K개의 감시 카메라가 감시하는 구간에 대한 정보가 주어졌을 때, 모든 방을 감시하기 위해 필요한 최소 감시 카메라 개수를 구하는 프로그램을 작성하시오.

입력 형식

첫 줄에 방의 개수 N과 감시 카메라의 개수 K가 주어진다. (3 ≤ N ≤ 10⁶, 1 ≤ K ≤ 10⁶)

다음 K개의 줄에 각 감시 카메라에 대한 정보 a_i와 b_i가 주어진다. (1 ≤ a_i, b_i, ≤ N)

a_i ≤ b_i 인 경우, a_i ≤ j ≤ b_i 를 만족하는 j번 방이 감시 받는다는 것을 의미하고, a_i > b_i 인 경우, 1 ≤ j ≤ b_i 혹은 a_i ≤ j ≤ N 을 만족하는 j번 방이 감시 받는다는 것을 의미한다.

출력 형식

홍준이가 모든 방을 감시하기 위해 필요한 감시 카메라의 최소 개수를 출력한다. 만약, 모든 방을 감시하는 것이 불가능하다면,  impossible을 출력한다.

예제 입력

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

예제 출력

3