Странная игра на графе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, Артур Флек живет со своей больной матерью. Чтобы хоть как-то ее развлечь, он предложил ей сыграть в занимательную настольную игру.

Первым делом Артур попросил мать нарисовать на листке бумаги с помощью простого карандаша неориентированный граф, не содержащий петель и кратных ребер. Затем по-очереди они будут делать ходы. Артур первым ходом выбирает некоторое ребро этого графа и стирает его. Каждым следующим ходом очередной игрок может выбрать ребро, которое было смежно стертому на предыдущем ходе. Напомним, что два ребра называются смежными, если они имеют общую вершину. Тот игрок, который не может сделать ход, проигрывает.

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

Артур не хочет задеть чувства матери, поэтому не планирует поддаваться. Зная граф, на котором будет проходить игра, помогите ему определить, сможет ли он выиграть или нет, если считать, что и он, и его мать будут стремиться выиграть, и будут играть оптимально.

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

В первой строке входных данных даны два натуральных числа $$$n$$$ и $$$m$$$ — число вершин и число ребер в графе ($$$2 \le n \le 10^4$$$, $$$1 \le m \le 10^4$$$).

В следующих $$$m$$$ строках даны пары чисел $$$a_i$$$, $$$b_i$$$ — номера вершин, которые соединяет $$$i$$$-е ребро ($$$1 \le a_i, b_i \le n$$$).

Гарантируется, что в графе нет петель и кратных ребер.

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

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

Примеры

Входные данные
7 5
1 2
5 1
5 6
3 2
2 4
Выходные данные
YES
Входные данные
3 2
1 2
2 3
Выходные данные
NO