KURSCHAK 1981 Problem 2

Let $n > 2$ be an even number. The squares of an $n\times n$ chessboard are coloured with $\frac12 n^2$ colours in such a way that every colour is used for colouring exactly two of the squares. Prove that one can place $n$ rooks on squares of $n$ different colours such that no two of the rooks can take each other.