(Challenge) Chef and Matching Game

These days, Chef has been playing a game. The game is played on a grid with $N$ rows (numbered $1$ through $N$) and $N$ columns (numbered $1$ through $N$); let's denote the cell in row $r$ and column $c$ by $(r, c)$. $2M$ cells $(X_1, Y_1), (X_2, Y_2), \ldots, (X_{2M}, Y_{2M})$ in the grid are marked. Chef wants to add exactly $M$ paths between pairs of distinct marked cells in such a way that n