← 返回题目列表

Codeforces · 53/E

E. 死胡同

中文机器翻译题面 查看原题

伯敦的生活变得艰难。这个城市有太多的道路,政府花费太多的钱来维护它们。有 n 个路口和 m 条双向道路,从每个路口都可以到达任何其他路口。市长想要关闭一些道路,以便剩下的道路总数达到 n - 1 条,并且仍然可以从每个路口到达任何其他路口。此外,市长还关心死胡同的数量,即只有一条路通行的路口。路口不应过多或过少。市长和他的助手们讨论了这个问题后决定,道路封闭后,路线图应该恰好包含 k 个死胡同。您的任务是计算满足以下条件的不同封闭道路方式的数量:

- 正好剩下 n - 1 条路。
- 可以从每个路口到达任何其他路口。
- 结果地图上正好有 k 个死胡同。

如果有一条道路在第一种路线中封闭,而在第二种路线中开放,则认为两种路线不同。

输入

第一行包含三个整数n、m和k(3 ≤ n ≤ 10、n - 1 ≤ m ≤ n·(n - 1) / 2、2 ≤ k ≤ n - 1),分别代表路口、道路和死胡同的数量。然后跟随 m 行,每行包含两个不同的整数 v1 和 v2 (1 ≤ v1, v2 ≤ n, v1 ≠ v2),它们代表另一条道路连接的路口数量。每对路口之间不能有多于一条道路。连接点用 1 到 n 的整数进行编号。保证从每个路口都能沿原路到达任意一个路口。

输出

打印单个数字 — 所需的方式数。

示例

输入 #1

3 3 2
1 2
2 3
1 3

输出 #1

3

输入 #2

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

输出 #2

12

输入 #3

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

输出 #3

4