import java.util.*;
WHITE, GRAY, BLACK; // Вводим тип данных, отвечающий за цвет вершины
}
class Main {
static final List<Color> color = new ArrayList<>(); // Список, в котором указаны цвета всех вершин
static final List<List<Integer>> crossroads = new ArrayList<>(); // Списки смежности перекрестков
public static void main
(String[] args
) { int n, m; // Количество перекрестков и дорог
Scanner in
= new Scanner
(System.
in); n = in.nextInt();
m = in.nextInt();
for (int i = 0; i < n; i++) {
color.
add(Color.
WHITE); // Окрашиваем все вершины в белый цвет }
for (int i = 0; i < n; i++) {
crossroads.add(new LinkedList<Integer>());
}
for (int i = 0; i < m; i++) {
int u, v; // Номер перекрестков, соединенных дорогой
u = in.nextInt();
v = in.nextInt();
u--;v--; // Так как по условию отсчёт начинается с первой вершины, вычитаем 1 для удобства
boolean isAlreadyRoad = false; // Проверяем, не повторяется ли дорога
List<Integer> uNeighbours = crossroads.get(u);
List<Integer> vNeighbours = crossroads.get(v);
if (!uNeighbours.isEmpty() && !vNeighbours.isEmpty()) {
if (uNeighbours.contains(v)) isAlreadyRoad = true;
}
if (!isAlreadyRoad) { // Проверка на повторение
uNeighbours.add(v); // Добавляем в список доступных перекрестков перекрестка u перекресток v
vNeighbours.add(u); // Аналогичные действия для перекрестка v, чтобы учесть возможность двусторонней езды
}
}
System.
out.
print(isTrack
(0,
0) ? "YES" : "NO"); // Запускаем метод, что ищет круговую трассу с первого перекрестка и выводим ответ }
public static boolean isTrack(int crossroad, int parent) { // Метод, проверяющий наличие круговой трассы
if (color.
get(crossroad
) == Color.
GRAY) return true; // Условие существования цикла color.
set(crossroad,
Color.
GRAY); List<Integer> crossroadNeighbours = crossroads.get(crossroad);
for (Integer nextCrossroad
: crossroadNeighbours
) { // Переход в соседние вершины if (parent != nextCrossroad && isTrack(nextCrossroad, crossroad)) return true; // Вход в вершину, в которую еще не входили
}
color.
set(crossroad,
Color.
BLACK); // Если дальше нет цикла, окрашиваем вершину в черный return false;
}
}
aW1wb3J0IGphdmEudXRpbC4qOwoKZW51bSBDb2xvciB7CiAgICBXSElURSwgR1JBWSwgQkxBQ0s7IC8vINCS0LLQvtC00LjQvCDRgtC40L8g0LTQsNC90L3Ri9GFLCDQvtGC0LLQtdGH0LDRjtGJ0LjQuSDQt9CwINGG0LLQtdGCINCy0LXRgNGI0LjQvdGLCn0KCmNsYXNzIE1haW4gewogICAgc3RhdGljIGZpbmFsIExpc3Q8Q29sb3I+IGNvbG9yID0gbmV3IEFycmF5TGlzdDw+KCk7IC8vINCh0L/QuNGB0L7Quiwg0LIg0LrQvtGC0L7RgNC+0Lwg0YPQutCw0LfQsNC90Ysg0YbQstC10YLQsCDQstGB0LXRhSDQstC10YDRiNC40L0KICAgIHN0YXRpYyBmaW5hbCBMaXN0PExpc3Q8SW50ZWdlcj4+IGNyb3Nzcm9hZHMgPSBuZXcgQXJyYXlMaXN0PD4oKTsgLy8g0KHQv9C40YHQutC4INGB0LzQtdC20L3QvtGB0YLQuCDQv9C10YDQtdC60YDQtdGB0YLQutC+0LIKCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgaW50IG4sIG07IC8vINCa0L7Qu9C40YfQtdGB0YLQstC+INC/0LXRgNC10LrRgNC10YHRgtC60L7QsiDQuCDQtNC+0YDQvtCzCiAgICAgICAgU2Nhbm5lciBpbiA9IG5ldyBTY2FubmVyKFN5c3RlbS5pbik7CiAgICAgICAgbiA9IGluLm5leHRJbnQoKTsKICAgICAgICBtID0gaW4ubmV4dEludCgpOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgICAgIGNvbG9yLmFkZChDb2xvci5XSElURSk7IC8vINCe0LrRgNCw0YjQuNCy0LDQtdC8INCy0YHQtSDQstC10YDRiNC40L3RiyDQsiDQsdC10LvRi9C5INGG0LLQtdGCCiAgICAgICAgfQogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgICAgIGNyb3Nzcm9hZHMuYWRkKG5ldyBMaW5rZWRMaXN0PEludGVnZXI+KCkpOwogICAgICAgIH0KICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG07IGkrKykgewogICAgICAgICAgICBpbnQgdSwgdjsgLy8g0J3QvtC80LXRgCDQv9C10YDQtdC60YDQtdGB0YLQutC+0LIsINGB0L7QtdC00LjQvdC10L3QvdGL0YUg0LTQvtGA0L7Qs9C+0LkKICAgICAgICAgICAgdSA9IGluLm5leHRJbnQoKTsKICAgICAgICAgICAgdiA9IGluLm5leHRJbnQoKTsKICAgICAgICAgICAgdS0tO3YtLTsgLy8g0KLQsNC6INC60LDQuiDQv9C+INGD0YHQu9C+0LLQuNGOINC+0YLRgdGH0ZHRgiDQvdCw0YfQuNC90LDQtdGC0YHRjyDRgSDQv9C10YDQstC+0Lkg0LLQtdGA0YjQuNC90YssINCy0YvRh9C40YLQsNC10LwgMSDQtNC70Y8g0YPQtNC+0LHRgdGC0LLQsAogICAgICAgICAgICBib29sZWFuIGlzQWxyZWFkeVJvYWQgPSBmYWxzZTsgLy8g0J/RgNC+0LLQtdGA0Y/QtdC8LCDQvdC1INC/0L7QstGC0L7RgNGP0LXRgtGB0Y8g0LvQuCDQtNC+0YDQvtCz0LAKICAgICAgICAgICAgTGlzdDxJbnRlZ2VyPiB1TmVpZ2hib3VycyA9IGNyb3Nzcm9hZHMuZ2V0KHUpOwogICAgICAgICAgICBMaXN0PEludGVnZXI+IHZOZWlnaGJvdXJzID0gY3Jvc3Nyb2Fkcy5nZXQodik7CiAgICAgICAgICAgIGlmICghdU5laWdoYm91cnMuaXNFbXB0eSgpICYmICF2TmVpZ2hib3Vycy5pc0VtcHR5KCkpIHsKICAgICAgICAgICAgICAgIGlmICh1TmVpZ2hib3Vycy5jb250YWlucyh2KSkgaXNBbHJlYWR5Um9hZCA9IHRydWU7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYgKCFpc0FscmVhZHlSb2FkKSB7IC8vINCf0YDQvtCy0LXRgNC60LAg0L3QsCDQv9C+0LLRgtC+0YDQtdC90LjQtQogICAgICAgICAgICAgICAgdU5laWdoYm91cnMuYWRkKHYpOyAvLyDQlNC+0LHQsNCy0LvRj9C10Lwg0LIg0YHQv9C40YHQvtC6INC00L7RgdGC0YPQv9C90YvRhSDQv9C10YDQtdC60YDQtdGB0YLQutC+0LIg0L/QtdGA0LXQutGA0LXRgdGC0LrQsCB1INC/0LXRgNC10LrRgNC10YHRgtC+0LogdgogICAgICAgICAgICAgICAgdk5laWdoYm91cnMuYWRkKHUpOyAvLyDQkNC90LDQu9C+0LPQuNGH0L3Ri9C1INC00LXQudGB0YLQstC40Y8g0LTQu9GPINC/0LXRgNC10LrRgNC10YHRgtC60LAgdiwg0YfRgtC+0LHRiyDRg9GH0LXRgdGC0Ywg0LLQvtC30LzQvtC20L3QvtGB0YLRjCDQtNCy0YPRgdGC0L7RgNC+0L3QvdC10Lkg0LXQt9C00YsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBTeXN0ZW0ub3V0LnByaW50KGlzVHJhY2soMCwgMCkgPyAiWUVTIiA6ICJOTyIpOyAvLyDQl9Cw0L/Rg9GB0LrQsNC10Lwg0LzQtdGC0L7QtCwg0YfRgtC+INC40YnQtdGCINC60YDRg9Cz0L7QstGD0Y4g0YLRgNCw0YHRgdGDINGBINC/0LXRgNCy0L7Qs9C+INC/0LXRgNC10LrRgNC10YHRgtC60LAg0Lgg0LLRi9Cy0L7QtNC40Lwg0L7RgtCy0LXRggogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgYm9vbGVhbiBpc1RyYWNrKGludCBjcm9zc3JvYWQsIGludCBwYXJlbnQpIHsgLy8g0JzQtdGC0L7QtCwg0L/RgNC+0LLQtdGA0Y/RjtGJ0LjQuSDQvdCw0LvQuNGH0LjQtSDQutGA0YPQs9C+0LLQvtC5INGC0YDQsNGB0YHRiwogICAgICAgIGlmIChjb2xvci5nZXQoY3Jvc3Nyb2FkKSA9PSBDb2xvci5HUkFZKSByZXR1cm4gdHJ1ZTsgLy8g0KPRgdC70L7QstC40LUg0YHRg9GJ0LXRgdGC0LLQvtCy0LDQvdC40Y8g0YbQuNC60LvQsAogICAgICAgIGNvbG9yLnNldChjcm9zc3JvYWQsIENvbG9yLkdSQVkpOwogICAgICAgIExpc3Q8SW50ZWdlcj4gY3Jvc3Nyb2FkTmVpZ2hib3VycyA9IGNyb3Nzcm9hZHMuZ2V0KGNyb3Nzcm9hZCk7CiAgICAgICAgZm9yIChJbnRlZ2VyIG5leHRDcm9zc3JvYWQgOiBjcm9zc3JvYWROZWlnaGJvdXJzKSB7IC8vINCf0LXRgNC10YXQvtC0INCyINGB0L7RgdC10LTQvdC40LUg0LLQtdGA0YjQuNC90YsKICAgICAgICAgICAgaWYgKHBhcmVudCAhPSBuZXh0Q3Jvc3Nyb2FkICYmIGlzVHJhY2sobmV4dENyb3Nzcm9hZCwgY3Jvc3Nyb2FkKSkgcmV0dXJuIHRydWU7IC8vINCS0YXQvtC0INCyINCy0LXRgNGI0LjQvdGDLCDQsiDQutC+0YLQvtGA0YPRjiDQtdGJ0LUg0L3QtSDQstGF0L7QtNC40LvQuAogICAgICAgIH0KICAgICAgICBjb2xvci5zZXQoY3Jvc3Nyb2FkLCBDb2xvci5CTEFDSyk7IC8vINCV0YHQu9C4INC00LDQu9GM0YjQtSDQvdC10YIg0YbQuNC60LvQsCwg0L7QutGA0LDRiNC40LLQsNC10Lwg0LLQtdGA0YjQuNC90YMg0LIg0YfQtdGA0L3Ri9C5CiAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgfQp9