Graph And Numbers
Contest: Educational Codeforces Round 73 (Rated for Div. 2)
Difficulty rating: 2900
Tags: bitmasks, brute force, combinatorics, dp, meet-in-the-middle

You are given an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. You have to write a number on each vertex of this graph, each number should be either $$$0$$$ or $$$1$$$. After that, you write a number on each edge equal to the sum of numbers on vertices incident to that edge.

You have to choose the numbers you will write on the vertices so that there is at least one edge with $$$0$$$ written on it, at least one edge with $$$1$$$ and at least one edge with $$$2$$$. How many ways are there to do it? Two ways to choose numbers are different if there exists at least one vertex which has different numbers written on it in these two ways.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 40$$$, $$$0 \le m \le \frac{n(n - 1)}{2}$$$) — the number of vertices and the number of edges, respectively.

Then $$$m$$$ lines follow, each line contains two numbers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) — the endpoints of the $$$i$$$-th edge. It is guaranteed that each pair of vertices is connected by at most one edge.

Output format:
Print one integer — the number of ways to write numbers on all vertices so that there exists at least one edge with $$$0$$$ written on it, at least one edge with $$$1$$$ and at least one edge with $$$2$$$.

Constraints:
Time limit: 3.5 s
Memory limit: 512.0 MB

Example input:
6 5
1 2
2 3
3 4
4 5
5 1

Example output:
20

Example input:
4 4
1 2
2 3
3 4
4 1

Example output:
4

Editorial:
Let $$$F(S)$$$ be the number of ways to paint the graph so that all numbers on edges belong to the set $$$S$$$. Using inclusion-exclusion we may get that the answer is $$$F(\{0, 1, 2\}) - F(\{1, 2\}) - F(\{0, 2\}) + F(\{2\}) - F(\{0, 1\}) + F(\{1\}) + F(\{0\}) - F(\{\})$$$.
Okay, let's analyze everything separatedly.
• $$$F(\{0, 1, 2\})$$$ is $$$2^n$$$, because every number is allowed;
• $$$F(\{1, 2\})$$$ will be analyzed later;
• $$$F(\{0, 2\})$$$ is $$$2^C$$$, where $$$C$$$ is the number of connected components — in each component we have to use the same number;
• $$$F(\{2\})$$$ is $$$2^I$$$, where $$$I$$$ is the number of isolated vertices — every non-isolated vertex should have number $$$1$$$ on it, and all isolated vertices may have any numbers;
• $$$F(\{0, 1\}) = F(\{1, 2\})$$$, since these cases are symmetric;
• $$$F(\{1\})$$$ is the number of bipartite colorings of the graph. It is $$$0$$$ if the graph contains an odd cycle, or $$$2^C$$$ if it is bipartite;
• $$$F(\{0\}) = F(\{2\})$$$, since these cases are symmetric;
• $$$F(\{\})$$$ is $$$2^n$$$ if there are no edges in the graph, otherwise it is $$$0$$$.
So, the only thing left to consider is $$$F(\{1, 2\})$$$. Actually, it is easier to calculate $$$F(\{0, 1\})$$$ — it is the number of independent sets of this graph. This problem is NP-complete, but when $$$n = 40$$$, we may apply meet-in-the-middle technique as follows:
1. divide all vertices into two sets $$$S_1$$$ and $$$S_2$$$ of roughly equal size;
2. for $$$S_1$$$, find all its independent subsets, and for each such subset, find which vertices from $$$S_2$$$ can be added to it without breaking its independency;
3. for each subset of $$$S_2$$$, find the number of independent subsets of $$$S_1$$$ such that no vertex from chosen subset of $$$S_2$$$ is adjacent to any vertex from chosen subset of $$$S_1$$$ (you may use subset DP and OR-convolution here);
4. find all independent subsets of $$$S_2$$$, and for every such subset, add the number of subsets of $$$S_1$$$ that can be merged with it so the resulting set is independent.
The most time-consuming part is counting all independent sets, so the time complexity is $$$(O(n2^{n/2}))$$$.