CF53E Dead Ends

Bertown的生活变得困难了起来。这个城市有太多的道路，而且政府花费了太多来维护这些道路。这里有$n$个节点和$m$条双向道路，且两两节点之间可以通过道路相互到达。现在市长想要关闭一些道路，使最后总共有$n-1$条道路留下，并且所以节点之间仍然联通。另外，市长很关心终点，也就是只有一条道路可以到达的点的数量。终点不能太多也不能太少。在讨论过这个问题之后，市长和他的助手们觉得在应该关闭的道路关闭后，应该总共有恰好$k$个终点。你的任务是求出满足以下三个条件的方案数： 1.有恰好$n-1$条道路保留下来； 2.整张道路图仍然联通； 3.最后有恰好$k$个终点在道路图上。 如果有一条道路在第一种方案中被关闭而在第二种方案中没有被关闭，那么我们认为这两种方案不同。

第一行有三个整数$n$，$m$和$k$（$3\leq n\leq10 , n-1\leq m\leq \frac {n(n-1)} {2} , 2\leq k\leq n-1$），依次代表了节点、道路和终点的数量。随后$m$行，每行包含两个不同的整数$v_1$和$v_2$（$1\leq v_1 , v_2\leq n , v_1 \not= v_2$），代表一条道路连接的两个节点。每一对节点之间最多有一条道路。节点被编号为1到$n$。保证初始的图联通。

一个整数：满足条件的方案数。