死亡之树

【题目描述】

如果一个$n$个点，$m$条无向边的图中(保证没有重边)的若干个点与连接它们的边组成的一棵树满足$n$个节点，$k$个叶子，则称这棵树为死亡之树。求这个图中有多少棵不同的死亡之树？ 叶子的定义:度数为$1$的节点。 树相同的定义：如果两棵树可以通过摆放，旋转转化为另一棵树的形状，则称之为相同的树。如 $2$与$1-2-3$为相同的一棵树。

 / \
1   3

 / \\\n1   3

【输入】

第一行两个整数$n，m，k$代表$n$个点$m$条边，最终需要有$k$个叶子； 接下来$m$行每行两个整数$a$，$b$表示$a$点与$b$点有一条边。

【输出】

一个整数，代表有多少棵死亡之树。

【输入样例】

3 3 2
1 2
2 3
1 3

【输出样例】

3

【提示】

【样例输入2】

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

【样例输出2】

4

【数据规模及约定】 对于40%的数据：$n≤10，m≤16$。 对于70%的数据：$n≤10，m≤23$。 对于100%的数据：$n≤10，m≤45$。

4 6 3\n1 2\n2 3\n3 4\n4 1\n1 3\n2 4

4