Problem Description
众所周知，度度熊喜欢图，尤其是联通的图。
今天，它在图上又玩出了新花样，新高度。有一张无重边的无向图， 求有多少个边集，使得删掉边集里的边后，图里恰好有K个连通块。
Input
第一行为T，表示输入数据组数。
对于每组数据，第一行三个整数N,M,K，表示N个点M条边的图。
接下来M行每行两个整数a,b，表示点a和点b之间有一条边。
1≤T≤20
1≤K≤N≤14
0≤M≤N∗(N+1)/2
1≤a,b≤N
Output
对第i组数据，输出
Case #i:
然后输出一行，仅包含一个整数，表示方法种数（对 1 000 000 009 取模） 。
Sample Input
3
1 0 1
1 1 1
1 1
3 3 2
1 2
2 3
1 3
Sample Output
Case #1:
1
Case #2:
2
Case #3:
3
