e-olymp
Задачи

Количество циклов

Количество циклов

Формально, путь в графе - это чередующаяся последовательность вершин и рёбер u1, e1, u2, e2, u3, ..., uk, начинающаяся и заканчивающаяся вершиной и такая, что любые соседние вершины и рёбра в ней инцидентны.

Цикл - это путь, начальная и конечная вершины которого совпадают. В цикле должно быть хотя бы одно ребро.

Простой путь отличается от обычного пути тем, что в нём не может быть повторяющихся вершин.

Простой цикл - это цикл, в котором нет повторяющихся вершин и рёбер.

Дан неориентированный граф. Посчитайте, сколько в нём различных простых циклов. Заметим, что циклы считаются одинаковыми, если они обходят одно и то же множество вершин в одном и том же порядке, возможно, начиная при этом из другой вершины, или если порядок обхода противоположный. Например, циклы с порядком обхода вершин 1, 2, 3, 1 и 2, 3, 1, 2 и 1, 3, 2, 1 считаются одинаковыми, а циклы 1, 2, 3, 4, 1 и 1, 3, 4, 2, 1 - нет, поскольку порядок обхода вершин различен.

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

В первой строке задано количество вершин n (1n10) и рёбер m в графе, соответственно. Следующие m строк содержат по два числа ui и vi (1ui, vin, uivi); каждая такая строка означает, что в графе существует ребро между вершинами ui и vi. В графе нет кратных рёбер.

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

Выведите количество простых циклов в заданном графе.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
3 2
1 2
2 3
Выходные данные #1
0
Входные данные #2
4 5
1 2
2 3
3 4
4 1
1 3
Выходные данные #2
3