Circular Network

N computers are connected in a circle. The computers are numbered from 1 to N, and each computer is connected by network lines to the computers on both sides. Computer 1 and computer N are also connected, so all lines together form one cycle.

Some of these lines will be converted to fiber-optic lines. You are given P requests, each asking for a fiber-optic path between computer p and computer q.

To satisfy one request, choose one of the two directions between p and q and convert every line on that path. For instance, if N=3 and computers 1 and 2 must be connected, you may convert only line 1-2, or you may convert lines 2-3 and 3-1.

Find the minimum number of lines that must be converted to satisfy all requests.

The first line contains two integers N and P. (1 ≤ N ≤ 1,000, 1 ≤ P ≤ 10,000)

Each of the next P lines contains two computer numbers p and q describing one request.

Print one integer X, the minimum number of lines needed to satisfy every request.