Задача D. Рыболовная сеть ≡

Условие

Дедушка Леонида — мастер по плетению рыболовных сетей. Для создания таких сетей требуется обладать должным талантом и терпением. Настоящие мастера плели свои сети очень прочными, используя при этом ровно одну цельную верёвку.

Сеть представляет N узлов, соединённых между собой M рёбрами. Будем считать, что сеть могла быть сплетена одной цельной верёвкой, если существует непрерывный путь, проходящий через каждое ребро ровно по одному разу. Путь должен начинаться и заканчиваться в узлах.

Леонид нашел на чердаке рыболовную сеть своего дедушки. Ему стало интересно, могла ли быть сплетена эта сеть ровно из одной цельной верёвки.

Требуется написать программу, которая считывает описание сети, и определяет, могла ли эта сеть быть сплетена ровно из одной цельной верёвки.

Формат входных данных

Первая строка содержит два целых числа N и M — количество узлов и рёбер у рыболовной сети соответственно.

Далее идёт M строк, в каждой из которых записано два целых числа u_i и v_i — номера узлов, между которыми проходит i-е ребро.

Гарантируется, что у каждого узла есть хотя бы одно ребро.

Обратите внимание, что у сети могут быть петли и кратные рёбра.

Пояснение

Петлёй называется ребро, соединяющее узел с самим собой.

Кратные ребра — два и более рёбер, соединяющих одну и ту же пару узлов.

Формат выходных данных

В единственной строке выведите "Yes" или "No" (без кавычек) — могла ли данная сеть быть сплетена ровно из одной цельной верёвки.

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ M ≤ 2 ⋅ 10⁵

1 ≤ u_i, v_i ≤ N

Описание подзадач и системы оценивания

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

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснение к примерам

Первая сеть могла быть сплетена следующим образом:

Примеры тестов

6 9
1 2
1 4
1 5
2 3
2 5
2 6
3 6
4 5
5 6

Yes

4 6
1 2
1 3
1 4
2 3
2 4
3 4

No

2 4
1 1
1 2
1 2
2 2

Yes

4 2
1 2
3 4

No

Разбор

Путь, описанный в задаче, также называется эйлеровым путём. Существует теорема, позволяющая быстро проверить наличие эйлерова пути в графе.

Теорема

Эйлеров путь существует тогда и только тогда, когда количество вершин с нечетным количеством рёбер равно нулю или двум.

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

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

Доказательство

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

Полное решение

Для полного решения задачи достаточно проверить наличие эйлерова пути в графе описанным способом: должно быть не более двух вершин с нечетным количеством рёбер.

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

Частичные решения

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

Вторая подзадача подразумевает квадратичное решение с поиском эйлерова пути в графе.

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