CPU

Students of the Computer Engineering and Informatics Department at the University of Patras, as part of their diploma project, are trying to design a low-cost processor that can be built on a circuit basis, using some digital circuits.

The circuits need to be connected together with cable connections. The connections must not intersect with the circuits or with other connections, but they do not necessarily have to follow straight lines.

The students have already made the basic design, in which all components are connected together in a loop, which we call the main loop. (These connections are from ~1~ to ~2~, from ~2~ to ~3~, ..., from ~N~ to ~1~). The circuits in the main loop are consecutively numbered.

To increase the processor's speed, some of the pairs of components need to be directly connected. For each component, it would be desirable to add at most one additional connection. The students have made a list of all the connections they want to add and have sorted them by priority. They will add the K most significant of these connections, where K should be as large as possible without causing cable intersections.

Problem:

Develop a program in one of the IOI languages ​​that will determine the maximum possible value of K.

Input Files:

Input files named cpu.in are text files with the following structure: The first line of the file contains an integer N (where ~1 \le~ N ~\le 200.000~) which represents the number of components already present in the main loop by the students. The second line contains an integer M (where ~1 \le~ M ~\le 50.000~), which represents the number of additional connections the students intend to add. The remaining M lines contain two positive integers ~P~ and ~Q~, indicating that the students want to connect component ~P~ to component ~Q~.

Note: There is no connection of a component with itself, each component can be connected to a neighboring component in the main loop. Connections are recorded in descending order of importance.

Output Files:

Output files named cpu.out are text files with the following structure: They have exactly one line containing a single integer, the maximum possible value of K.

Examples of Input - Output Files

STDIN (cpu.in)

8
4
1 4
3 6
2 5
7 8

STDOUT (cpu.out)

2

Explanation of the Example:

The connections ~1~-~4~ and ~3~-~6~ are added. Then, the connection ~2~-~5~ imposes a crossover, so it cannot be added.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 4 sec.