CF793G Oleg and chess

Oleg the bank client solves an interesting chess problem: place on $ n×n $ chessboard the maximum number of rooks so that they don't beat each other. Of course, no two rooks can share the same cell. Remind that a rook standing in the cell $ (a,b) $ beats a rook standing in the cell $ (x,y) $ if and only if $ a=x $ or $ b=y $ . Unfortunately (of fortunately?) for Oleg the answer in this problem was always $ n $ , so the task bored Oleg soon. He decided to make it more difficult by removing some cells from the board. If a cell is deleted, Oleg can't put a rook there, but rooks do beat each other "through" deleted cells. Oleg deletes the cells in groups, namely, he repeatedly choose a rectangle with sides parallel to the board sides and deletes all the cells inside the rectangle. Formally, if he chooses a rectangle, lower left cell of which has coordinates $ (x_{1},y_{1}) $ , and upper right cell of which has coordinates $ (x_{2},y_{2}) $ , then he deletes all such cells with coordinates $ (x,y) $ that $ x_{1}

N/A

N/A

Here is the board and the example of rooks placement in the first example: