CF1221G Graph And Numbers

给定一个无向图，包含 $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$。

由 ChatGPT 4.1 翻译