| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 12 | 5 | 5 | 41.667% |
Как известно, Артур Флек живет со своей больной матерью. Чтобы хоть как-то ее развлечь, он предложил ей сыграть в занимательную настольную игру.
Первым делом Артур попросил мать нарисовать на листке бумаги с помощью простого карандаша неориентированный граф, не содержащий петель и кратных ребер. Затем по-очереди они будут делать ходы. Артур первым ходом выбирает некоторое ребро этого графа и стирает его. Каждым следующим ходом очередной игрок может выбрать ребро, которое было смежно стертому на предыдущем ходе. Напомним, что два ребра называются смежными, если они имеют общую вершину. Тот игрок, который не может сделать ход, проигрывает.
На рисунке представлена возможная последовательность действий в данной игре. Пунктиром отмечены ребра, которые будут стерты в процессе игры. На ребрах, которые будут стерты, написаны числа, показывающие порядок стирания этих ребер.
Артур не хочет задеть чувства матери, поэтому не планирует поддаваться. Зная граф, на котором будет проходить игра, помогите ему определить, сможет ли он выиграть или нет, если считать, что и он, и его мать будут стремиться выиграть, и будут играть оптимально.
В первой строке входных данных даны два натуральных числа $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