Пушистая помеха
Пушистая помеха
Для того, чтобы защитить себя от злых кроликов, Фредди решил установить автоматическую систему для обнаружения их в фотографиях с камер наблюдения. Сложное программное обеспечение обнаруживает важные моменты в картинке и линиях между ними. К сожалению, местность на фотографиях довольно разнообразна и много точек и линий на самом деле не кролики.
Вы сделали следующее наблюдение: каждый кролик имеет четыре лапы и тело, соединяющее их. Основываясь на этом наблюдении напишите программу, которая определит, может ли заданная картина содержать кролика.
Входные данные
Состоит из нескольких тестов. Первая строка содержит два числа n и m (0 ≤ n ≤ 10000, 0 ≤ m ≤ 20000) - количество точек и линий на изображении. Каждая из следующих m строк содержит два разных целых числа x и y (1 ≤ x, y ≤ n), указывающих на то что точки x и y непосредственно соединены прямой. Считайте, что каждая пара точек соединена как минимум одной прямой линией и никакая точка не соединена сама с собой.
Выходные данные
Для каждого теста вывести "YES", если картинка может содержать кролика, и "NO" иначе. Картинка содержит кролика, если можно удалить некоторые точки и прямые так, чтобы результирующее изображение было связным и содержало в точности 4 лапы. Изображение называется связным, если (и только если) любые две точки соединены друг с другом одной или несколькими последовательными линиями. Лапой называется точка, соединенная только с одной другой точкой.
Пример
2 1 1 2 5 4 1 2 1 3 1 4 1 5
NO YES