Eulerian Subgraphs

题目描述

给出一个无向图，图中有 n 个节点和 m 条边。 我们考虑包含原图所有节点且只包含其中一部分边的子图。如果每个节点的度都是偶数，则称该子图为欧拉子图。 你的任务是计算欧拉子图的数量对 $10^9+7$ 取模。

输入格式

第一行包含两个整数 n 和 m：节点数和边数。节点编号为 1,2,\dots,n。 接下来有 m 行描述边。每行包含两个整数 a 和 b：表示在节点 a 和 b 之间有一条边。任意两节点之间至多有一条边，且每条边连接两个不同的节点。

输出格式

输出欧拉子图的数量对 $10^9+7$ 取模。

4 3
1 2
1 3
2 3

2

提示

$1 \le n \le 10^5$ $0 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$ 样例解释：你可以选择保留所有边或删除所有边，所以共有两个可能的欧拉子图。

标签: CSES2078|先进技术

来源

CSES2078|先进技术