Chess Puzzle
Why are you so upset? You'll never succeed like this!
Folklore
Little girl Dasha is trying to solve a chess puzzle.
The challenge is to place the fewest number of queens on an n×n chessboard so that every square is under attack. However, some squares are off-limits for placing queens. A queen in chess can move any distance diagonally, vertically, or horizontally, but cannot jump over another queen. A queen attacks the square it occupies and all squares it can move to.
Help Dasha by writing a program to solve this puzzle.
Input
The input begins with a line containing two integers n and k, separated by a space. These represent the size of the board and the number of prohibited squares, respectively (3 ≤ n ≤ 10, 0 ≤ k ≤ n^2). The following k lines each contain two integers r and c, separated by a space, indicating the coordinates of a prohibited square (1 ≤ r, c ≤ n). All prohibited squares are distinct.
Output
The output should start with a single integer m, the minimum number of queens needed. The next m lines should list the coordinates of the squares where the queens are placed. If there are multiple valid solutions, any one of them can be printed. If no solution is possible, output the number -1.