CF1221G.Graph And Numbers

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.

给你一个包含 $n$ 个顶点和 $m$ 条边的无向图。你需要在图的每个顶点上写一个数，该数只能是 $0$ 或 $1$。接着，你在每条边上写一个数，其值等于与该边关联的两个顶点上的数字之和。

你需要选择顶点上的数字，使得图中至少有一条边上写的数是 $0$，至少有一条边上写的数是 $1$，且至少有一条边上写的数是 $2$。问：满足条件的顶点赋值方案共有多少种？若两种赋值方案中存在至少一个顶点被赋予了不同的数字，则认为这两种方案不同。

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.

第一行包含两个整数 $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$ 条边的两个端点。保证任意一对顶点之间至多有一条边相连。

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$.

输出一个整数——表示在所有顶点上写数字的方式数目，使得至少存在一条边上的数字为 $0$，至少存在一条边上的数字为 $1$，且至少存在一条边上的数字为 $2$。