IV математическая олимпиада «Шелковый путь», 2005 год

Найдите все пары натуральных чисел $(m, n)$, при которых возможно раскрасить каждую клетку клетчатой доски размера $m \times n$ в белый или черный цвета так, чтобы для любой клетки доски количество соседних клеток одинакового цвета с ней было нечетным. Две клетки называются $\textit{соседними}$, если они различные и имеют хотя бы одну общую вершину.