Задача 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