6743. 欧拉子图 (Eulerian Subgraphs)
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 给定一个包含 $n$ 个节点和 $m$ 条边的无向图。 我们考虑保留原图的所有节点及部分边所构成的子图。如果一个子图中每个节点的度数均为偶数，则称该子图为“欧拉子图”。 你的任务是计算欧拉子图的数量，结果对 $10^9+7$ 取模。 ## 输入格式 第一行包含两个整数 $n$ 和 $m$，分别表示节点数和边数。节点编号为 $1, 2, \dots, n$。 接下来 $m$ 行描述边。每行包含两个整数 $a$ 和 $b$，表示节点 $a$ 和节点 $b$ 之间存在一条边。 任意两个节点之间最多只有一条边，且每条边都连接两个不同的节点。 ## 输出格式 输出一个整数，表示欧拉子图的数量模 $10^9+7$ 的结果。 ## 输入输出样例 ### 输入 #1 ``` 4 3 1 2 1 3 2 3 ``` ### 输出 #1 ``` 2 ``` ### 样例解释 你可以选择保留所有边，或者移除所有边（此时所有点度数为 $0$，仍是偶数），因此共有 $2$ 种可能的欧拉子图。 ## 说明/提示 ### 数据规模与约定 * $1 \le n \le 10^5$ * $0 \le m \le 2 \cdot 10^5$ * $1 \le a, b \le n$