G. Граф и числа
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан неориентированный граф из $$$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$$$.

Примеры
Входные данные
6 5
1 2
2 3
3 4
4 5
5 1
Выходные данные
20
Входные данные
4 4
1 2
2 3
3 4
4 1
Выходные данные
4
Входные данные
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