Minimum Camera Coverage

The International Corporation for Protection and Control (ICPC) has its headquarters in the shape of a convex polygon with n sides (walls). There are m available positions where cameras can be installed. Each camera monitors a consecutive range of walls. Specifically, each camera is described by two integers \(l\) and \(r\):

If \(l \le r\), then the camera covers walls \(l, l+1, \ldots, r\). Otherwise, if \(l > r\), it covers walls \(l, l+1, \ldots, n, 1, 2, \ldots, r\). That is, the interval wraps around. The goal is to choose as few cameras as possible so that every wall of the building is monitored by at least one camera.

If it is impossible to cover all the walls with the available cameras, output -1.

Note: Consider the walls arranged in a circle, and use the concept of circular intervals. One can use the formula for a wrapping interval as follows: if an interval is represented as \([l, r]\) and \(l > r\), then it is equivalent to \([l, r+n]\) when the circle is "unwrapped".

inputFormat

The first line contains two integers n and m where n is the number of walls and m is the number of available camera positions. Each of the next m lines contains two integers (l) and (r), denoting that a camera placed in that position covers the range of walls from (l) to (r). If (l \le r), the camera covers walls (l) through (r); if (l > r), it covers walls (l, l+1, \ldots, n, 1, 2, \ldots, r).

outputFormat

Output a single integer representing the minimum number of cameras required to cover all walls of the building. If it is impossible to cover all walls, output -1.

sample

6 3
1 3
4 6
6 2

2