Задача N. Семь колонн Владивостока

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Когда абитуриент Дима пришёл в кампус ДВФУ на день открытых дверей, его внимание привлекла инсталляция "Семь колонн Владивостока".

Данная инсталляция является рабочим макетом объекта, спроектированного для создания в бетоне в городской среде. В основе идеи лежат наблюдения за природой и инфраструктурой города и их взаимодействием. Данный образ, семь колонн, является символом диалога между силами природы и деятельностью человека.

Каждому объекту данной скульптурной группы соответствует одна из семи самых высоких сопок города Владивостока. Высоты объектов, а также расстояния между объектами пропорциональны реальным высотам и расстояниям. На вершине каждого объекта находится фрагмент породы соответствующей сопки. Высоты выполнены в масштабе 1:75, расстояния между объектами соответственно 1:100.

Поскольку Дима дополнительно изучает информатику, он быстро смекнул, что данная конструкция может быть представлена как планарный граф, т.е. граф, который можно нарисовать на плоскости без пересечений рёбер.

Дима знает, как посчитать число граней этого планарного графа, для этого нужно применить формулу Эйлера V − E + F = 2, где V — число вершин, E — число рёбер, F — число граней, включая внешнюю грань. В нашем случае V = 7, E = 13, отсюда F = 8, поэтому треугольных граней всего 7, что легко проверить.

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

Напишите программу, принимающую на вход данный граф и вычисляющую количество элементарных циклов в этом графе.

Формат входного файла

Входной файл содержит целые числа N M — количество вершин и количество рёбер соответственно. Далее следуют M пар целых чисел — рёбра графа.

Ребро не может идти из вершины в неё саму. В графе нет повторяющихся рёбер. Ребра (u, v) и (v, u) — это одно и то же ребро.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество элементарных циклов.

Ограничения

2 ≤ N ≤ 7

M ≥ 1

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7 13
1 2
1 3
2 3
2 5
2 6
3 4
3 5
3 7
4 5
4 6
4 7
5 6
6 7
56
2
6 6
1 2
2 3
3 1
4 6
6 5
5 4
2
3
4 6
1 2
1 3
1 4
2 3
2 4
3 4
7

0.121s 0.009s 17