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