eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Пушистая помеха

Пушистая помеха

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Для того, чтобы защитить себя от злых кроликов, Фредди решил установить автоматическую систему для обнаружения их в фотографиях с камер наблюдения. Сложное программное обеспечение обнаруживает важные моменты в картинке и линиях между ними. К сожалению, местность на фотографиях довольно разнообразна и много точек и линий на самом деле не кролики.

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

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

Состоит из нескольких тестов. Первая строка содержит два числа n и m (0n10000, 0m20000) - количество точек и линий на изображении. Каждая из следующих m строк содержит два разных целых числа x и y (1x, yn), указывающих на то что точки x и y непосредственно соединены прямой. Считайте, что каждая пара точек соединена как минимум одной прямой линией и никакая точка не соединена сама с собой.

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

Для каждого теста вывести "YES", если картинка может содержать кролика, и "NO" иначе. Картинка содержит кролика, если можно удалить некоторые точки и прямые так, чтобы результирующее изображение было связным и содержало в точности 4 лапы. Изображение называется связным, если (и только если) любые две точки соединены друг с другом одной или несколькими последовательными линиями. Лапой называется точка, соединенная только с одной другой точкой.

Пример

Входные данные #1
2 1
1 2
5 4
1 2
1 3
1 4
1 5
Выходные данные #1
NO
YES
Источник 2013 ACM ICPC Czech Technical University (CTU) Open Contest, Prague, Problem С