Формально, путь в графе - это чередующаяся последовательность вершин и рёбер u[1]
, e[1]
, u[2]
, e[2]
, u[3]
, ..., u[k]
, начинающаяся и заканчивающаяся вершиной и такая, что любые соседние вершины и рёбра в ней инцидентны.
Цикл - это путь, начальная и конечная вершины которого совпадают. В цикле должно быть хотя бы одно ребро.
Простой путь отличается от обычного пути тем, что в нём не может быть повторяющихся вершин.
Простой цикл - это цикл, в котором нет повторяющихся вершин и рёбер.
Дан неориентированный граф. Посчитайте, сколько в нём различных простых циклов. Заметим, что циклы считаются одинаковыми, если они обходят одно и то же множество вершин в одном и том же порядке, возможно, начиная при этом из другой вершины, или если порядок обхода противоположный. Например, циклы с порядком обхода вершин 1, 2, 3, 1 и 2, 3, 1, 2 и 1, 3, 2, 1 считаются одинаковыми, а циклы 1, 2, 3, 4, 1 и 1, 3, 4, 2, 1 - нет, поскольку порядок обхода вершин различен.
В первой строке задано количество вершин n (1 ≤ n ≤ 10) и рёбер m в графе, соответственно. Следующие m строк содержат по два числа u[i]
и v[i]
(1 ≤ u[i]
, v[i]
≤ n, u[i]
≠ v[i]
); каждая такая строка означает, что в графе существует ребро между вершинами u[i]
и v[i]
. В графе нет кратных рёбер.
Выведите количество простых циклов в заданном графе.