Rook Path

There is a chessboard with $N$ rows (numbered $1$ through $N$) and $N$ columns (numbered $1$ through $N$). $M$ squares on this chessboard (numbered $1$ through $M$) are marked. For each valid $i$, the $i$-th of the marked squares is in the $r_i$-th row and $c_i$-th column. You should perform the following process: - First, you take a rook and put this rook on one of the marked squares. - Then