3. Долой списывание!

Задача

Необходимо определить, можно ли разделить лкшат на две группы так, чтобы каждое наблюдаемое списывание происходило между представителями разных групп.

Входные данные

Во входном файле содержатся числа $N$ и $M$ — количество лкшат и количество пар, обменявшихся записками ($1 \leqslant N \leqslant 100$, $0 \leqslant M \leqslant \tfrac{N(N-1)}{2}$). Далее следуют $M$ строк, каждая содержит два различных числа — номера лкшат, обменявшихся записками. Каждая пара встречается не более одного раза.

Выходные данные

Выведите YES, если лкшат можно разбить на две группы, и NO в противном случае.

Пример

стандартный ввод      стандартный вывод
3 2                    YES
1 2
2 3

Ограничения

  • Время: 2 секунды
  • Память: 64 мегабайта
Редакционный разбор Рассматриваем граф как неориентированный и красим его в два цвета обходом в глубину или ширину. Для каждой ещё не окрашенной вершины запускаем обход, присваивая стартовой цвет $1$, а всем соседям — $-1$. Если при посещении соседа обнаруживаем, что он уже окрашен и цвет совпадает с текущим, граф не двудольный и ответ «NO». Если обход завершился без конфликтов (в том числе когда рёбер нет), граф двудольный — значит, можно разделить лкшат на две группы, и ответ «YES». Временная сложность $O(N + M)$.

Mentioned by