cstdio
Stu.yxr
呵呵酵母菌
_Horizon
wangxh
mikumikumi
cstdio【试题来源】
2011中国国家集训队命题答辩
【问题描述】
有N个点（编号1到N）组成的无向图，已经为你连了M条边。请你再连K条边，使得所有的点的度数都是偶数。求有多少种连的方法。要求你连的K条边中不能有重边，但和已经连好的边可以重。不允许自环的存在。求连边的方法数。我们只关心它模10007的余数。
【输入格式】
输入的第一行有三个自然数，分别表示点数N，已经连好的边数M，和你要连的边数K。保证K≤N(N-1)/2
接下来M行每行两个整数x,y，描述了一条连接x和y的边。
30%的数据满足：
N≤200
100%的数据满足：
N≤1000，M≤N，K≤1000，K≤N(N-1)/2
接下来M行每行两个整数x,y，描述了一条连接x和y的边。
30%的数据满足：
N≤200
100%的数据满足：
N≤1000，M≤N，K≤1000，K≤N(N-1)/2
【输出格式】
输出一个整数，表示连边的方法数模10007的余数
【样例输入】
5 1 4
1 2
1 2
【样例输出】
13
【样例说明】
以下是13种连边的方法（只显示你连的边）：
{(1,2),(1,3),(1,4),(3,4)}
{(1,2),(1,3),(1,5),(3,5)}
{(1,2),(1,4),(1,5),(4,5)}
{(1,2),(2,3),(2,4),(3,4)}
{(1,2),(2,3),(2,5),(3,5)}
{(1,2),(2,4),(2,5),(4,5)}
{(1,2),(3,4),(3,5),(4,5)}
{(1,3),(2,4),(3,5),(4,5)}
{(1,3),(2,5),(3,4),(4,5)}
{(1,4),(2,3),(3,5),(4,5)}
{(1,4),(2,5),(3,4),(3,5)}
{(1,5),(2,3),(3,4),(4,5)}
{(1,5),(2,4),(3,4),(3,5)}
{(1,2),(1,3),(1,4),(3,4)}
{(1,2),(1,3),(1,5),(3,5)}
{(1,2),(1,4),(1,5),(4,5)}
{(1,2),(2,3),(2,4),(3,4)}
{(1,2),(2,3),(2,5),(3,5)}
{(1,2),(2,4),(2,5),(4,5)}
{(1,2),(3,4),(3,5),(4,5)}
{(1,3),(2,4),(3,5),(4,5)}
{(1,3),(2,5),(3,4),(4,5)}
{(1,4),(2,3),(3,5),(4,5)}
{(1,4),(2,5),(3,4),(3,5)}
{(1,5),(2,3),(3,4),(4,5)}
{(1,5),(2,4),(3,4),(3,5)}