A International Corporation for Protection and Control (ICPC) desenvolve tecnologia eficiente para, bem, proteção e controlo. Naturalmente, tem grande interesse em que a sua própria sede seja protegida e controlada. Vista de cima, a sede tem a forma de um polígono convexo. Existem vários locais adequados à sua volta onde podem ser instaladas câmaras para vigiar o edifício. Cada câmara cobre um determinado intervalo dos lados do polígono (paredes do edifício), dependendo da sua posição. A ICPC quer minimizar o número de câmaras necessárias para cobrir todo o edifício.

Entrada

A entrada consiste num único caso de teste. A primeira linha contém dois inteiros $n$ e $k$ ($3 \le n \le 10^6$ e $1 \le k \le 10^6$), onde $n$ é o número de paredes e $k$ é o número de locais possíveis para instalar câmaras. Cada uma das restantes $k$ linhas contém dois inteiros $a_i$ e $b_i$ ($1 \le a_i, b_i \le n$). Estes inteiros especificam as paredes que uma câmara no local $i$ cobriria. Se $a_i \le b_i$, a câmara cobre cada parede $j$ tal que $a_i \le j \le b_i$. Se $a_i > b_i$, a câmara cobre cada parede $j$ tal que $a_i \le j \le n$ ou $1 \le j \le b_i$.

Saída

Apresente o número mínimo de câmaras suficiente para cobrir todas as paredes do edifício. Os intervalos cobertos por duas câmaras podem sobrepor-se. Se não for possível cobrir o edifício, apresente impossible em vez disso.

Exemplos

Entrada 1

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

Saída 1

3

Entrada 2

8 2
8 3
5 7

Saída 2

impossible

Entrada 3

8 2
8 4
5 7

Saída 3

2