시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB92231923.457%

문제

체스에 사용되는 말 중 하나인 나이트는 아래 표의 S와 같은 위치에서 X와 같은 위치로  이동할 수 있다. 이 때 이동하려는 위치에 다른 말이 있으면 그 말을 잡아먹을 수 있다.

N×N 크기의 체스판이 주어졌을 때, 이 체스판에 한 번의 이동으로는 서로를 잡아먹을 수 없도록 놓을 수 있는 나이트의 최대 개수를 구하는 프로그램을 작성하시오. 단, 체스판의 M개의 주어진 위치에는 나이트를 놓을 수 없다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), M(0 ≤ M ≤ N2)이 주어진다. 다음 M개의 줄에는 나이트를 놓을 수 없는 위치들이 주어진다. 각 위치는 체스판의 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, N)으로 하여 주어진다.

출력

첫째 줄에 서로 잡을 수 없도록 놓을 수 있는 최대의 나이트 수를 출력한다.

예제 입력 1

3 2
1 1
3 3

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjMzOTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWM3NzRcdWQyYjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2NiNFx1YzJhNFx1YzVkMCBcdWMwYWNcdWM2YTlcdWI0MThcdWIyOTQgXHViOWQwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzggXHViMDk4XHVjNzc0XHVkMmI4XHViMjk0IFx1YzU0NFx1Yjc5OCBcdWQ0NWNcdWM3NTggU1x1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFhcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzcwNFx1Y2U1OFx1Yjg1YyAmbmJzcDtcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjU0YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjRcdWIyOTQgXHVjNzA0XHVjZTU4XHVjNWQwIFx1YjJlNFx1Yjk3OCBcdWI5ZDBcdWM3NzQgXHVjNzg4XHVjNzNjXHViYTc0IFx1YWRmOCBcdWI5ZDBcdWM3NDQgXHVjN2ExXHVjNTQ0XHViYTM5XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNWRjMDFhZGEtYjU1MC00Y2Q3LTgxZjYtOTg0NWE2ODYwOWM0XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAxNDdweDsgaGVpZ2h0OiAxNDdweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+TiZ0aW1lcztOIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1YzVkMCBcdWQ1NWMgXHViYzg4XHVjNzU4IFx1Yzc3NFx1YjNkOVx1YzczY1x1Yjg1Y1x1YjI5NCBcdWMxMWNcdWI4NWNcdWI5N2MgXHVjN2ExXHVjNTQ0XHViYTM5XHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIzYzRcdWI4NWQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMDk4XHVjNzc0XHVkMmI4XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjJlOCwgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzU4IE1cdWFjMWNcdWM3NTggXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzcwNFx1Y2U1OFx1YzVkMFx1YjI5NCBcdWIwOThcdWM3NzRcdWQyYjhcdWI5N2MgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggTigxICZsZTsgTiAmbGU7IDIwMCksIE0oMCAmbGU7IE0gJmxlOyBOPHN1cD4yPFwvc3VwPilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMDk4XHVjNzc0XHVkMmI4XHViOTdjIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YzcwNFx1Y2U1OFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM3MDRcdWNlNThcdWIyOTQgXHVjY2I0XHVjMmE0XHVkMzEwXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWM3MDRcdWI5N2MgKDEsIDEpLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4XHViOTdjIChOLCBOKVx1YzczY1x1Yjg1YyBcdWQ1NThcdWM1ZWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMTFjXHViODVjIFx1YzdhMVx1Yzc0NCBcdWMyMTggXHVjNWM2XHViM2M0XHViODVkIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMFx1Yzc1OCBcdWIwOThcdWM3NzRcdWQyYjggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMzkxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS25pZ2h0cyIsImRlc2NyaXB0aW9uIjoiPHA+V2UgYXJlIGdpdmVuIGEgY2hlc3MtYm9hcmQgb2Ygc2l6ZSBuJnRpbWVzO24sIGZyb20gd2hpY2ggc29tZSBmaWVsZHMgaGF2ZSBiZWVuIHJlbW92ZWQuIFRoZSB0YXNrIGlzIHRvIGRldGVybWluZSB0aGUgbWF4aW11bSBudW1iZXIgb2Yga25pZ2h0cyB0aGF0IGNhbiBiZSBwbGFjZWQgb24gdGhlIHJlbWFpbmluZyBmaWVsZHMgb2YgdGhlIGJvYXJkIGluIHN1Y2ggYSB3YXkgdGhhdCBub25lIG9mIHRoZW0gY2hlY2sgZWFjaCBvdGhlci48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81ZGMwMWFkYS1iNTUwLTRjZDctODFmNi05ODQ1YTY4NjA5YzRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDE0N3B4OyBoZWlnaHQ6IDE0N3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWcuMTogQSBrbmlnaHQgcGxhY2VkIG9uIHRoZSBmaWVsZCBTIGNoZWNrcyBmaWVsZHMgbWFya2VkIHdpdGggeC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtLCB0aGF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIHRoZSBkZXNjcmlwdGlvbiBvZiBhIGNoZXNzLWJvYXJkIHdpdGggc29tZSBmaWVsZHMgcmVtb3ZlZCwgZnJvbSB0aGUgaW5wdXQ8XC9saT5cclxuXHQ8bGk+ZGV0ZXJtaW5lcyB0aGUgbWF4aW11bSBudW1iZXIgb2Yga25pZ2h0cyB0aGF0IGNhbiBiZSBwbGFjZWQgb24gdGhlIGNoZXNzLWJvYXJkIGluIHN1Y2ggYSB3YXkgdGhhdCBub25lIG9mIHRoZW0gY2hlY2sgZWFjaCBvdGhlciw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSByZXN1bHQgdG8gdGhlIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBuIGFuZCBtLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIDEgJmxlOyBuICZsZTsgMjAwLCAwICZsZTsgbSAmbHQ7IG48c3VwPjI8XC9zdXA+OyBuIGlzIHRoZSBjaGVzcy1ib2FyZCBzaXplIGFuZCBtIGlzIHRoZSBudW1iZXIgb2YgcmVtb3ZlZCBmaWVsZHMuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBtIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VyczogeCBhbmQgeSwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCAxICZsZTsgeCwgeSAmbGU7IG4gLS0gdGhlc2UgYXJlIHRoZSBjb29yZGluYXRlcyBvZiB0aGUgcmVtb3ZlZCBmaWVsZHMuIFRoZSBjb29yZGluYXRlcyBvZiB0aGUgdXBwZXIgbGVmdCBjb3JuZXIgb2YgdGhlIGJvYXJkIGFyZSAoMSwxKSwgYW5kIG9mIHRoZSBib3R0b20gcmlnaHQgYXJlIChuLG4pLiBUaGUgcmVtb3ZlZCBmaWVsZHMgYXJlIG5vdCByZXBlYXRlZCBpbiB0aGUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCZuYnNwO3Nob3VsZCBjb250YWluIG9uZSBpbnRlZ2VyIChpbiB0aGUgZmlyc3QgYW5kIG9ubHkgbGluZSkuIEl0IHNob3VsZCBiZSB0aGUgbWF4aW11bSBudW1iZXIgb2Yga25pZ2h0cyB0aGF0IGNhbiBiZSBwbGFjZWQgb24gdGhlIGdpdmVuIGNoZXNzLWJvYXJkIHdpdGhvdXQgY2hlY2tpbmcgZWFjaCBvdGhlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d