e-olymp
Yarışlar

Cycles in the graph

Автогонки

В городе N в ближайшее время состоится этап чемпионата мира по автогонкам среди автомобилей класса Формула-0. Поскольку специальный автодром для этих соревнований организаторы построить не успели, было решено организовать трассу на улицах города.

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

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

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

Напишите программу, которая по заданному списку дорог города определит, возможна ли организация в городе требуемой круговой трассы.

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

Первая строка содержит два целых числа: n (1 n 1000) - количество перекрёстков в городе N и m (0 m 100000) - количество дорог в составленном списке.

Последующие m строк описывают дороги. Каждая дорога описывается двумя числами: u и v (1u, vn, uv) - номера перекрёстков, которые она соединяет. Так как дороги двустронние, то пара чисел (u, v) и пара чисел (v, u) описывают одну и ту же дорогу.

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3 4
1 2
2 3
3 1
3 2
Çıxış verilənləri #1
YES
Giriş verilənləri #2
2 3
1 2
2 1
2 1
Çıxış verilənləri #2
NO