The 8 Queens problem is a classic problem of placing 8 Queens on a 8x8 chess board such that no two Queens can attack each other. In short, the 8 Queens must be placed such that no two of them lie in the same row, column or diagonal. The image below shows 1 possible solution.
We count rotations and reflections as different solutions so for the 8 Queens problem, it is known that there are 92 solutions. Since I've already told you this answer, we shall make the problem more general. The problem will be generalised to the N queens problem on an NxN chess board. To make things more interesting, there will be Q queens initially placed on the chess board and B squares that cannot have queens placed on them. Count the number of solutions to the N queens problem satisfying all the above restrictions.
For all test cases, 0 ≤ Q,B ≤ N2
Subtask 1 (7%): 1 ≤ N ≤ 4
Subtask 2 (11%): N = 8
Subtask 3 (14%): N = 10
Subtask 4 (19%): N = 12
Subtask 5 (22%): N = 13
Subtask 6 (26%): N = 14
Subtask 7 (0%): 15 ≤ N ≤ 16
Subtask 8 (1%): 1 ≤ N ≤ 20, Q=0, B=0
The first line of input will consist of a single integer N. The next line of input will consist of a single integer Q and the next Q lines will contain two integers 1 ≤ X,Y ≤ N that means that there is queen initially placed on the Xth row and Yth column. The next line of input will consist of a single integer B and the next B lines will contain two integers 1 ≤ X,Y ≤ N that means that there cannot be a queen placed on the Xth row and Yth column.
The output should only be a single integer representing the number of different solutions satisfying the restrictions given. Note that rotations and reflections are considered distinct solutions, and that it is possible that no solutions exist given the restrictions.