题目描述

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

 / \
1   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$。

树的计数说明

按输入图的顶点编号与所选边集区分生成树；原文旋转示意只说明同一边集的画法不重复计数。三角形样例输出3而非1，明确不同顶点/边的同构路径仍分别计数。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。