Проверка на двудольность графа

Граф считается двудольным, если его можно раскрасить в два цвета так, чтобы никакие две соседние вершины не были окрашены одинаково.

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

Вам задан неориентированный граф с числом вершин v и числом рёбер e. Необходимо проверить, является ли данный граф двудольным.

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

В первой строке входных данных содержатся два целых числа v (1 ≤ v ≤ 100 000) и e (1 ≤ e ≤ 100 000).

В следующих e строках записаны пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), где указывается, что вершина v1 соединена с вершиной v2, и наоборот.

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

Программа должна вывести Yes, если заданный граф двудольный, и No — в противном случае.

Примеры