给出 个点 条边的(没有自环但可能有重边的)无向图,要求给每个点分配 条或 条与它相邻的边,使得每条边被分配恰好一次,求方案数。答案对 取模。
alliance.in
第一行两个正整数 ,其中 。
下面 行,每行两个正整数 表示一条无向边 ,其中 。
alliance.out
一行一个整数表示答案。
5 4 1 2 3 2 4 5 4 5
6
样例 的 种方案如下。
个数分别代表第 条边被分配给了哪个点:
{2, 3, 4, 5} {2, 3, 5, 4} {1, 3, 4, 5} {1, 3, 5, 4} {1, 2, 4, 5} {1, 2, 5, 4}
6 5 1 2 2 3 3 4 1 4 2 4
0