Олимпиадный тренинг

Задача . G. Граф и числа


Вам задан неориентированный граф из \(n\) вершин и \(m\) ребер. Вы должны написать число на каждой вершине графа, каждое число должно быть равно \(0\) или \(1\). После этого на каждом ребре будет записана сумма чисел на двух вершинах, инцидентных этому ребру.

Вы должны выбрать числа таким образом, чтобы было хотя бы одно ребро с числом \(0\), хотя бы одно ребро с числом \(1\) и хотя бы одно ребро с числом \(2\). Сколько способов так расставить числа? Два способа различны, если существует хотя бы одна вершина, на которой в разных способах записаны разные числа.

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

В первой строке заданы два целых числа \(n\) и \(m\) (\(1 \le n \le 40\), \(0 \le m \le \frac{n(n - 1)}{2}\)) — количество вершин и ребер, соответственно.

Затем следуют \(m\) строк, в каждой из которых записаны два целых числа \(x_i\) и \(y_i\) (\(1 \le x_i, y_i \le n\), \(x_i \ne y_i\)) — вершины, соединяемые \(i\)-м ребром. Гарантируется, что между каждой парой вершин существует не более одного ребра.

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

Выведите одно целое число — количество способов так записать числа на вершинах, что есть хотя бы одно ребро с числом \(0\), хотя бы одно ребро с числом \(1\) и хотя бы одно ребро с числом \(2\).


Примеры
№Входные данныеВыходные данные
1
6 5
1 2
2 3
3 4
4 5
5 1
20
2
4 4
1 2
2 3
3 4
4 1
4
3
35 29
1 2
2 3
3 1
4 1
4 2
3 4
7 8
8 9
9 10
10 7
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
34201047040
Статистика успешных решений по компиляторам
 Кол-во
С++5