Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
Xiang-qi is a kind of traditional Chinese chess. There is a special role in the game called “Jiang” (or called “Shuai”). When you want to operate this kind of role, it can only dominating the four neighbor cell and can of course attack the role there (In fact there is a special condition can allow the role attack farther distance but we ignore this condition).
Now we have an N*N chessboard, we want to place some “Jiang” on it. Of course we have several restraints on placing chess pieces:
1. The placing chess role cannot dominate each other.
2. On the chessboard all cells without placing chess should be dominated.
3. There are some cells called “Hole” which cannot be placed by chess piece. Attention that the hole should also be dominated.
For a given chessboard, we want to know the least number of chess pieces to place which can satisfy the restraints above.
There are multiple test cases.
In each test case, the first line contains two integers N and K indicating the size of the chessboard and the number of the holes on the chessboard. (1 <= N <= 9, 0 <= K <= N*N)
In the next K line each line contains two integers x and y indicating the cell (x, y) is a hole cell. (1 <= x, y <= N)
You can get more details from the sample and hint.
For each test case, you should output an integer indicating the answer of the test case. If there is no way to place the chess pieces, please output -1.
In the sample we can have several ways to placing the chess pieces:
Place on (1, 3), (2, 1) and (3, 2);
Place on (3, 1), (1, 2) and (2, 3);
Although place on (1, 2), (2, 2) and (3, 2) can dominate all cell but it is not satisfy the first restraint. And place on (1, 1), (1, 3) and (3, 2) is also illegal because the cell (1, 1) is a hole.