Гамильтонов цикл
Вам дан неориентированный граф с n вершинами и e рёбрами. Ваша задача — определить, содержит ли этот граф гамильтонов цикл.
Входные данные
Первая строка содержит два целых числа n (1 ≤ n ≤ 20) и e (0 ≤ e ≤ ), которые обозначают количество вершин и рёбер в графе соответственно.
В следующих e строках описаны рёбра графа. Каждая такая строка содержит два целых числа a и b (1 ≤ a, b ≤ n, a ≠ b), указывающие на ребро между вершинами a и b.
Выходные данные
Выведите YES, если в графе существует гамильтонов путь или цикл. В противном случае выведите NO.
Примеры
Входные данные | Выходные данные |
|---|---|
3 3 1 2 2 3 3 1 | YES |
4 4 1 2 2 3 3 1 2 4 | NO |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB