Rooks Placing

The first line of input contains an integer ‘T’ denoting the number of test cases. The description of ‘T’ test cases follows. The first line of each test case contains two space-separated integers ‘n’ and ‘m’ representing dimensions of the chessboard and the number of rooks that are already present in the chessboard respectively. Then ‘m’ line follows, each containing 2 space-separated integers ‘r’, ‘c’ representing that there is a rook at cell (r, c).

For each test case, print in one line an integer ‘k’ representing the maximum number of additional rooks that can be placed on the chessboard and then print ‘k’ lines each of which contains 2 space-separated integers ‘r’ and ‘c’ representing that a rook is placed at cell (r, c). You need to print these cells in lexicographical order.

1 <= T <= 50 1 <= n <= 10^4 0 <= m <= n 0 <= r, c < n Where ‘T’ is the number of test cases and ‘n’ is the dimensions of the chessboard, ‘m’ is the number of rooks that are already present on the chessboard, and (r, c) represents the cell of the chessboard. Time Limit: 1 sec

Test case 1 : There is 4*4 chessboard with 2 rooks placed at cell (0, 3) and (1, 1). Here you can place at most two additional rooks. If you try to place more than two additional rooks then there definitely exist an attacking pair of rooks. There are two possible ways to place these additional 2 rooks, The lexicographical order of cells of these possible ways are following-: 1. (2, 0), (3, 2) 2. (2, 2), (3, 0) (2, 0), (3, 2) is the lexicographically smallest of them. So it will be the answer. Test case 2 : You cannot place any additional rooks here. No matter where you place the rook it will attack at least one other rook.

Test case 1 : There is only one cell in the chessboard, so you can place one rook at that cell. Test case 2 : You can place one additional rook at cell (2, 0). If you try to place a rook at any other position then there definitely exist an attacking pair of rooks.

Brute Force

Create a boolean matrix of order n * n. Initially, all the cells of the matrix will be false.
Iterate over the given array having positions of already placed rooks, and for each rook at cell (r, c) mark true at cell (r, c) in the boolean matrix.
Create a vector of arrays to store the positions of the additional rooks. Let's name it ‘result’.
Run a nested loop where the outer loop ‘i’ ranges from 0 to n-1 and the inner loop ‘j’ ranges from 0 to n-1, and for each pair (i, j) do the following:
- If the value in the boolean matrix at cell (i, j) is true then we cannot place rook at the cell (i, j).
- Otherwise, run a loop where ‘k’ ranges from 0 to n-1, and for each ‘k’ check whether there exists any cell (i, k) or (k, j) which has the value true in the boolean matrix. If no such cell exists then mark (i, j) true in the boolean matrix and appends the cell (i, j) in the vector ‘result’.
Return ‘result’, it will now have the position of additional rooks in lexicographical order and its size is maximum possible.

Time Complexity

O(n^3), where ‘n’ is the dimensions of the chessboard.

There are three nested loops: the outermost loop, the innermost loop, and the middle loop each run for ‘n’ times.

Space Complexity

O(n^2), where ‘n’ is the dimensions of the chessboard.

Space used by the boolean matrix is of order n^2.

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation of the Sample Input1 :

Sample Input 2 :

Sample Output 2 :

Explanation of the Sample Input 2 :