KöMaL 2016 A673

We have colour pearls placed on an $n\times n$ board; a square may contain more than one pearl. Altogether we used $2n-1$ colours and $n$ pearls from each colour. The pearls are arranged in such a way that no row or column contains more than one pearl of the same colour. Prove that it is possible to select $n$ pearls with distinct colours such that no two of them are in the same row or column.