Вам задан неориентированный граф из \(n\) вершин и \(m\) ребер. Вы должны написать число на каждой вершине графа, каждое число должно быть равно \(0\) или \(1\). После этого на каждом ребре будет записана сумма чисел на двух вершинах, инцидентных этому ребру.
Вы должны выбрать числа таким образом, чтобы было хотя бы одно ребро с числом \(0\), хотя бы одно ребро с числом \(1\) и хотя бы одно ребро с числом \(2\). Сколько способов так расставить числа? Два способа различны, если существует хотя бы одна вершина, на которой в разных способах записаны разные числа.
Выходные данные
Выведите одно целое число — количество способов так записать числа на вершинах, что есть хотя бы одно ребро с числом \(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
|