Surveillance Cameras

Interview

Time limit4sMemory limit512 MB

Summary

Choose the fewest circular arcs that cover all N rooms on a circle, or report impossible.

Level: Medium6 of 10
Topics: Greedy, Intervals, Sorting
Solved: No attempts yet

Problem

N rooms sit on a circle. K cameras each watch a contiguous arc, possibly wrapping: if $a_i \le b_i$ then rooms $a_i$ through $b_i$ ; if $a_i > b_i$ then rooms $1$ through $b_i$ and $a_i$ through N.

Find the minimum number of cameras needed to watch every room. Print impossible if it cannot be done.

Input

Line 1: $N$ , $K$ .
Next $K$ lines: $a_i$ , $b_i$ .

Output

Minimum number of cameras, or impossible.

Examples5

Example 1

Input

Expected output

Example 2
Input
```
5 3
1 3
2 4
4 2
```
Expected output
```
2
```
Example 3
Input
```
8 2
1 8
3 6
```
Expected output
```
1
```

Example 4

Input

Expected output

impossible

Example 5

Input

Expected output

impossible