시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 133 8 6 20.000%

문제

한 회사의 N(1≤N≤1,000)개의 컴퓨터들이 원형 네트워크로 연결되어 있다. 컴퓨터에는 차례로 1, 2, …, N의 번호가 붙어 있는데, x번 컴퓨터는 x-1번 컴퓨터와 x+1번 컴퓨터와 네트워크 회선으로 연결되어 있다. 그리고 1번 컴퓨터는 N번 컴퓨터와 네트워크 회선으로 연결이 되어 있어서 전체적으로 원의 모양으로 연결되어 있다.

이 회사에서는 자주 사용되는 일부 회선을 광섬유로 전환하기로 하였다. 이를 위해 사전 조사를 실시한 결과, p번 컴퓨터와 q번 컴퓨터 사이에 광섬유를 설치해 달라는 요청이 총 P(1≤P≤10,000)개 접수되었다.

p번 컴퓨터와 q번 컴퓨터 사이에 광섬유를 설치하는 방법은 시계 방향과 시계 반대 방향의 두 가지가 있다. 예를 들어 N=3이고, 1번 컴퓨터와 2번 컴퓨터 사이에 광섬유를 설치해 달라는 요청이 있었다고 하자. 이 때에 1-2를 연결하는 방법도 있고, 2-3, 3-1을 연결하는 방법도 있다.

최소 개수의 회선을 광섬유로 전환하여 P개의 요청을 모두 만족시키는 방법을 찾으라.

입력

첫째 줄에 두 정수 N, P가 주어진다. 다음 P개의 줄에는 p, q들이 주어진다.

출력

첫째 줄에 최소 개수 X를 출력한다.

예제 입력

5 2
1 3
5 4

예제 출력

3

힌트