## Knights

## BOI 2001 Day 2 Problem 1## Knights
We are given a chess-board of size
Fig.1: A knight placed on the field S checks fields marked with x. ## TaskWrite a program, that:- reads the description of a chess-board with some fields removed, from the input file
`kni.in`, - 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,
- writes the result to the output file
`kni.out`.
## InputThe first line of the input filekni.in 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 in the file.
## OutputThe output filekni.out should contain one integer (in the first and only line of the file).
It should be the maximum number of knights that can be placed on the given chess-board without checking each other.
## Sample Input3 2 1 1 3 3 ## Sample Output5SubmitStatistics |