\begin{tutorial}{Games of Chess}

{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Фёдор Ушаков\\
         Разработка: & Фёдор Ушаков\\
     \end{tabular}
}

Рассмотрим задачу в терминах теории графов. Нам дан неориентированный связный граф, и нужно раскрасить его вершины в некоторое число цветов так, чтобы для каждой вершины $u$ число вершин $v$ того же цвета, соединённых с $u$ ребром, было нечётным.

При нечётном $n$ ответа не существует. Действительно, предположим обратное: пусть существует какая-то допустимая раскраска. Оставим в графе только те рёбра, концы которых имеют одинаковый цвет. После этой операции у каждой вершины степень нечётна, и так как вершин нечётное число, сумма степеней всех вершин нечётна. А в неориентированном графе сумма степеней всех вершин должна быть чётной, так как каждое ребро прибавляет к этой сумме $2$. Противоречие.

Для чётного $n$ ответ всегда существует, и его можно найти с помощью следующего алгоритма:

\begin{enumerate}
\item Построим дерево обхода в глубину (DFS).
\item Повторяем, пока есть вершины:
\begin{itemize}
\item Возьмём самый глубокий лист $v$. Посмотрим на его родителя $u$. У $u$ есть $k$ детей, все они --- листья.
\item Если $k$ нечётно, то покрасим поддерево $u$ в один цвет и отрежем от остального дерева.
\item Если $k$ чётно, но есть хотя бы один лист, из которого есть хотя бы одно обратное ребро, ведущее наверх в некоторого предка вершины $u$, то этот лист переподвесим к ближайшей вершине, в которую из него есть ребро, а остальную часть поддерева отрежем так же, как в предыдущем пункте.
\item Если $k$ чётно, но рёбер наверх из листьев нет, то отрежем все эти листья и пометим, что их в конце надо будет покрасить так же, как вершину $u$, а саму вершину $u$ оставим в дереве.
\end{itemize}
\end{enumerate}

Можно показать, что раскраска графа по данному алгоритму является корректной. При аккуратной реализации сложность этого решения составит $O(n + m)$.

\end{tutorial}
