시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB207403041.096%

문제

한 회사의 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를 출력한다.

예제 입력 1

5 2
1 3
5 4

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjIyMTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZDBcdWQ2MTUgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NWMgXHVkNjhjXHVjMGFjXHVjNzU4IE4oMSAmbGU7IE4gJmxlOyAxLDAwMClcdWFjMWNcdWM3NTggXHVjZWY0XHVkNGU4XHVkMTMwXHViNGU0XHVjNzc0IFx1YzZkMFx1ZDYxNSBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjZWY0XHVkNGU4XHVkMTMwXHVjNWQwXHViMjk0IFx1Y2MyOFx1Yjg0MFx1Yjg1YyAxLCAyLCAmaGVsbGlwOywgTlx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjI5NFx1YjM3MCwgeFx1YmM4OCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWIyOTQgeC0xXHViYzg4IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1YzY0MCB4KzFcdWJjODggXHVjZWY0XHVkNGU4XHVkMTMwXHVjNjQwIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2YyBcdWQ2OGNcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIDFcdWJjODggXHVjZWY0XHVkNGU4XHVkMTMwXHViMjk0IE5cdWJjODggXHVjZWY0XHVkNGU4XHVkMTMwXHVjNjQwIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2YyBcdWQ2OGNcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHVjNzc0IFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWMxMWMgXHVjODA0XHVjY2I0XHVjODAxXHVjNzNjXHViODVjIFx1YzZkMFx1Yzc1OCBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1ZDY4Y1x1YzBhY1x1YzVkMFx1YzExY1x1YjI5NCBcdWM3OTBcdWM4ZmMgXHVjMGFjXHVjNmE5XHViNDE4XHViMjk0IFx1Yzc3Y1x1YmQ4MCBcdWQ2OGNcdWMxMjBcdWM3NDQgXHVhZDExXHVjMTJjXHVjNzIwXHViODVjIFx1YzgwNFx1ZDY1OFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWM3MDRcdWQ1NzQgXHVjMGFjXHVjODA0IFx1Yzg3MFx1YzBhY1x1Yjk3YyBcdWMyZTRcdWMyZGNcdWQ1NWMgXHVhY2IwXHVhY2ZjLCBwXHViYzg4IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1YzY0MCBxXHViYzg4IFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVhZDExXHVjMTJjXHVjNzIwXHViOTdjIFx1YzEyNFx1Y2U1OFx1ZDU3NCBcdWIyZWNcdWI3N2NcdWIyOTQgXHVjNjk0XHVjY2FkXHVjNzc0IFx1Y2QxZCBQKDEgJmxlOyBQICZsZTsgMTAsMDAwKVx1YWMxYyBcdWM4MTFcdWMyMThcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPnBcdWJjODggXHVjZWY0XHVkNGU4XHVkMTMwXHVjNjQwIHFcdWJjODggXHVjZWY0XHVkNGU4XHVkMTMwIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWFkMTFcdWMxMmNcdWM3MjBcdWI5N2MgXHVjMTI0XHVjZTU4XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVhY2ZjIFx1YzJkY1x1YWNjNCBcdWJjMThcdWIzMDAgXHViYzI5XHVkNWE1XHVjNzU4IFx1YjQ1MCBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IE49M1x1Yzc3NFx1YWNlMCwgMVx1YmM4OCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWM2NDAgMlx1YmM4OCBcdWNlZjRcdWQ0ZThcdWQxMzAgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWQxMVx1YzEyY1x1YzcyMFx1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NzQgXHViMmVjXHViNzdjXHViMjk0IFx1YzY5NFx1Y2NhZFx1Yzc3NCBcdWM3ODhcdWM1YzhcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM3NzRcdWI1NGNcdWM1ZDAgMS0yXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWIzYzQgXHVjNzg4XHVhY2UwLCAyLTMsIDMtMVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWQ2OGNcdWMxMjBcdWM3NDQgXHVhZDExXHVjMTJjXHVjNzIwXHViODVjIFx1YzgwNFx1ZDY1OFx1ZDU1OFx1YzVlYyBQXHVhYzFjXHVjNzU4IFx1YzY5NFx1Y2NhZFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViOWNjXHVjODcxXHVjMmRjXHVkMGE0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWNjM2VcdWM3M2NcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggTiwgUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBQXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBwLCBxXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMTggWFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjIxNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpYmVyIENvbW11bmljYXRpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiB3YW50cyB0byBjb25uZWN0IGhpcyBOICgxICZsdDs9IE4gJmx0Oz0gMSwwMDApIGJhcm5zIChudW1iZXJlZCAxLi5OKSB3aXRoIGEgbmV3IGZpYmVyLW9wdGljIG5ldHdvcmsuIEhvd2V2ZXIsIHRoZSBiYXJucyBhcmUgbG9jYXRlZCBpbiBhIGNpcmNsZSBhcm91bmQgdGhlIGVkZ2Ugb2YgYSBsYXJnZSBwb25kLCBzbyBoZSBjYW4gb25seSBjb25uZWN0IHBhaXJzIG9mIGFkamFjZW50IGJhcm5zLiBUaGUgY2lyY3VsYXIgY29uZmlndXJhdGlvbiBtZWFucyB0aGF0IGJhcm4gTiBpcyBhZGphY2VudCB0byBiYXJuIDEuPFwvcD5cclxuXHJcbjxwPkZKIGRvZXNuJiMzOTt0IG5lZWQgdG8gY29ubmVjdCBhbGwgdGhlIGJhcm5zLCB0aG91Z2gsIHNpbmNlIG9ubHkgY2VydGFpbiBwYWlycyBvZiBjb3dzIHdpc2ggdG8gY29tbXVuaWNhdGUgd2l0aCBlYWNoIG90aGVyLiBIZSB3YW50cyB0byBjb25zdHJ1Y3QgYXMgZmV3PGJyIFwvPlxyXG5jb25uZWN0aW9ucyBhcyBwb3NzaWJsZSB3aGlsZSBzdGlsbCBlbmFibGluZyBhbGwgb2YgdGhlc2UgcGFpcnMgdG8gY29tbXVuaWNhdGUgdGhyb3VnaCB0aGUgbmV0d29yay4gR2l2ZW4gdGhlIGxpc3Qgb2YgYmFybnMgdGhhdCB3aXNoIHRvIGNvbW11bmljYXRlIHdpdGggZWFjaCBvdGhlciwgZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIG51bWJlciBvZiBsaW5lcyB0aGF0IG11c3QgYmUgbGFpZC4gVG8gY29tbXVuaWNhdGUgZnJvbSBiYXJuIDEgdG8gYmFybiAzLCBsaW5lcyBtdXN0IGJlIGxhaWQgZnJvbSBiYXJuIDEgdG8gYmFybiAyIGFuZCBhbHNvIGZyb20gYmFybiAyIHRvIGJhcm4gMyhvciBqdXN0IGZyb20gYmFybiAzIHRvIDEsaWYgbj0zKS48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUd28gaW50ZWdlcnMsIE4gYW5kIFAgKHRoZSBudW1iZXIgb2YgY29tbXVuaWNhdGlvbiBwYWlycywgMSAmbHQ7PSBQICZsdDs9IDEwLDAwMCk8XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uUCsxOiB0d28gaW50ZWdlcnMgZGVzY3JpYmluZyBhIHBhaXIgb2YgYmFybnMgYmV0d2VlbiB3aGljaCBjb21tdW5pY2F0aW9uIGlzIGRlc2lyZWQuIE5vIHBhaXIgaXMgZHVwbGljYXRlZCBpbiB0aGUgbGlzdC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPk9uZSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciB3aGljaCBpcyB0aGUgbWluaW11bSBudW1iZXIgb2YgZGlyZWN0IGNvbm5lY3Rpb25zIEZKIG5lZWRzIHRvIG1ha2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==