ELMO 2012 Problem 2

Find all ordered pairs of positive integers $(m,n)$ for which there exists a set $C=\{c_1,\ldots,c_k\}$ ( $k\ge1$ ) of colors and an assignment of colors to each of the $mn$ unit squares of a $m\times n$ grid such that for every color $c_i\in C$ and unit square $S$ of color $c_i$ , exactly two direct (non-diagonal) neighbors of $S$ have color $c_i$ .

David Yang.