In the world of chess, the knight moves in an L-shape: two squares in one direction and then one square perpendicular, or one square in one direction and then two squares perpendicular. This unique movement allows it to jump over other pieces, reaching eight possible squares from a central position on an empty board.
Possible moves of a knight in a chess board Given a chessboard of size $$$N \times N$$$ and $$$K$$$ knights placed on it, determine the minimum number of knights that must be removed from the board so that no two knights are attacking each other. A knight is considered to be attacking another knight if it can move to the square occupied by the second knight in one turn based on its L-shaped movement pattern.
The first line of input contains two integer numbers separated by a space $$$N$$$ ($$$3 \leq N \leq 25$$$), and $$$K$$$ ($$$1 \leq K \leq N*N$$$), representing the size of the board, and the number of knights in the board.
Each of the following $$$K$$$ lines contains two integer numbers $$$r_i$$$, $$$c_i$$$, representing the $$$i$$$-th knight is placed on row $$$r_i$$$ and column $$$c_i$$$ in the board. No two knights will be places on the same position.
Output a line with an integer number, the minimum number of knights that should be removed from the board so that no two knights are attacking each other.
3 41 11 22 12 2
0
5 93 31 22 11 42 44 15 24 55 4
2
3 91 12 33 13 23 31 21 32 12 2
4
