Пошук клік
Пошук клік
Класичною задачею у теорії графів є задача знаходження клік. Розглянемо неорієнтовний граф з n вершин. Кліка – це повний підграф, тобто, це такий набір з k вершин, що усі можливі ребра між цими k вершинами існують. У цій задачі вас також запитують, чи існують кліки у заданому графі. Щоб спростити задачу, вам задано, що k = 4, тобто, ви шукаєте кліки розміру 4.
Вхідні дані
Вхідні дані будуть містити декілька наборів. Перший рядок кожного набору складається з двох цілих чисел - кількості вершин n (n < 20) та числа ребер m (m < 100). Другий рядок набору містить m пар чисел, кожна з яких позначає наявність відповідного неорієнтовного ребра. Вершини перенумеровано від 1 до n. У списку ребер немає повторень. Останній рядок містить 0 0 та не обробляється.
Вихідні дані
Для кожного тесту вивести в окремому рядку YES або NO у залежності від того, чи містить граф кліку розміру 4 чи ні.
4 6 1 2 2 3 3 4 4 1 1 3 2 4 0 0
YES