Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 1 задач <---
Источники --> Командные олимпиады --> Московская командная олимпиада --> 9-11 классы --> 2013
    Лига А(10 задач)
    Лига Б(9 задач)
Страница: 1 Отображать по:
#111846
Карта метро
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В одном уездном городе Эн было решено построить собственное метро. Все силы города были мобилизованы на выкапывание станций и прокладку подземных путей дедовскими лопатами.

Вся эта история нас бы совершенно не интересовала, если бы однажды в мэрию города не пришло письмо из далёкой страны Емакира. Оказалось, что компания Alpep подозревает администрацию уездного города в нарушении их патента на jMetro и грозится возбудить против города Эн дело. Согласно патенту, jMetro — это метро, в котором:

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

Поскольку компания Alpep известна своими необоснованными обвинениями в нарушениях патентов, мэрия города хочет проверить правомочность заявления компании.

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

В первой строке заданы два числа N и M ( 1 ≤ N , M ≤ 2·10 5 ) — количество станций метро и перегонов между ними. Следующие M строк содержат описания перегонов: каждая из них содержит по два числа — номера станций, между которыми есть перегон. По каждому перегону составы могут ездить как в одну, так и в другую сторону. Между любыми двумя станциями существует не более одного перегона. Никакой перегон не соединяет станцию саму с собой.

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

Выведите « YES », если метро уездного города Эн нарушает патент jMetro, и « NO » в противном случае.

Примечание

Первый пример соответствует рисунку из условия.

Примеры
Входные данные
15 19
1 4
4 11
2 10
3 2
8 7
7 6
12 10
15 10
11 2
14 9
6 13
7 9
7 11
2 5
8 3
6 10
3 6
11 3
12 3
Выходные данные
YES
Входные данные
5 4
2 1
2 3
2 5
2 4
Выходные данные
NO
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест