Chess Puzzle#1163
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 minimum number of queens on an n \times n chessboard so that every square is under attack. Some squares are prohibited for placing queens. A queen moves any distance diagonally, vertically, or horizontally, limited only by the edge of the board, and 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.
The first line contains two space-separated integers and – the size of the board and the number of prohibited squares (3 \le n \le 10, 0 \le k \le n^2). Each of the next lines contains two space-separated integers and – the coordinates of a prohibited square (1 \le r, c \le n). All prohibited squares are distinct.
The first line should contain a single integer – the minimum number of queens required. The next lines should contain the coordinates where the queens are placed. If there are multiple valid solutions, print any of them. If there is no solution, output only -1.
Example 1