CPU

Aiden is designing a low-cost processor to be assembled on a circuit board from standard components. Components are joined by connecting wires. A wire may bend freely and need not be straight, but it must never cross a component or another wire.

The basic layout is already finished: all $N$ components are wired together into a single closed loop, the main loop, and they lie around this loop in consecutive order, numbered $1$ through $N$. To speed the processor up, Aiden now wants to add some extra direct wires between pairs of components. Each component may receive at most one extra wire.

He has written down every extra connection he would like, ordered from most important to least important. He will keep the $K$ most important of them — the first $K$ entries of the list — with $K$ chosen as large as possible so that all kept wires can be drawn simultaneously without any two of them crossing.

Since the components lie on a loop, each extra wire can be routed either inside the loop or outside it. Two wires placed on the same side cross exactly when their endpoints alternate around the loop; wires on opposite sides never cross. Hence a set of connections can be drawn without crossings if and only if every connection can be assigned to the inside or the outside so that no two connections on the same side have interleaving endpoints.

Given the loop size and the importance-ordered list of desired connections, determine the largest possible value of $K$.

The first line contains an integer $N$ ($1 < N < 200000$), the number of components on the main loop.

The second line contains an integer $M$ ($1 < M < 50000$), the number of extra connections under consideration.

Each of the next $M$ lines contains two integers $P$ and $Q$ ($1 \le P, Q \le N$, $P \ne Q$): a desired connection between components $P$ and $Q$. The connections are given in descending order of importance. No connection joins a component to itself, a component may be joined to a neighbouring component of the main loop, and no component appears in more than one connection.

Print a single integer: the largest possible value of $K$.