#1027. 「USACO 2012.1 Gold」Bovine Alliance

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
alliance.in ≫ alliance.out
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

给出 个点 条边的(没有自环但可能有重边的)无向图,要求给每个点分配 条或 条与它相邻的边,使得每条边被分配恰好一次,求方案数。答案对 取模。

输入格式 alliance.in

第一行两个正整数 ,其中

下面 行,每行两个正整数 表示一条无向边 ,其中

输出格式 alliance.out

一行一个整数表示答案。

样例

输入 #1

5 4 
1 2 
3 2 
4 5 
4 5

输出 #1

6

解释 #1

样例 种方案如下。

个数分别代表第 条边被分配给了哪个点:

{2, 3, 4, 5} 
{2, 3, 5, 4} 
{1, 3, 4, 5} 
{1, 3, 5, 4} 
{1, 2, 4, 5} 
{1, 2, 5, 4} 

输入 #2

6 5
1 2
2 3
3 4
1 4
2 4

输出 #2

0