5 人解决，14 人已尝试。
16 份提交通过，共有 71 份提交。
8.3 EMB 奖励。
1465. Knights
单点时限: 10.0 sec
内存限制: 256 MB
We are given a chess-board of size n*n, from which some fields have been removed. The task is to determine the maximum number of knights that can be placed on the remaining fields of the board in such a way that none of them check each other.
Fig.1: A knight placed on the field S checks fields marked with x.
Write a program, that:
1.reads the description of a chess-board with some fields removed, from the input,
2.determines the maximum number of knights that can be placed on the chess-board in such a way that none of them check each other,
3.writes the result out.
输入格式
The first line contains two integers n and m, separated by a single space, 1<=n<=200, 0<=m<n^2; n is the chess-board size and m is the number of removed fields. Each of the following m lines contains two integers: x and y, separated by a single space, 1<=x,y<=n – these are the coordinates of the removed fields. The coordinates of the upper left corner of the board are (1,1), and of the bottom right are (n,n). The removed fields are not repeated.
输出格式
The output should contain one integer (in the first and only line). It should be the maximum number of knights that can be placed on the given chess-board without checking each other.
样例
Input
3 2 1 1 3 3
Output
5
题目标签