CSES2078 欧拉子图
#CS2078. 欧拉子图
欧拉子图
题目背景
翻译自 CSES-2078 题。
题目描述
给定一个无向图，图中有 n 个节点和 m 条边。
我们考虑包含原图中所有节点且部分边的子图。如果一个子图是欧拉子图，那么它的每个节点的度数必须是偶数。
你的任务是计算欧拉子图的数量，并对 109+710^9 + 7109+7 取模。
输入格式
第一行输入两个整数 n 和 m，分别表示节点的数量和边的数量。节点编号为 1,2,...,n1, 2, ..., n1,2,...,n。
接下来的 m 行，每行描述一条边。每行包含两个整数 a 和 b，表示节点 a 和节点 b 之间有一条边。每两个节点之间最多有一条边，并且每条边连接的是不同的节点。
输出格式
输出一个整数，表示欧拉子图的数量，结果对 109+710^9 + 7109+7 取模。
样例
4 3
1 2
1 3
2 3
2
样例1解释 既可以保留所有边，也可以删除所有边，因此有两种可能的欧拉子图。
说明/提示