伯敦的生活变得艰难。这个城市有太多的道路,政府花费太多的钱来维护它们。有 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