时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
Bobo has a connected undirected simple graph with n vertices and m edges. The vertices are numbered by 1, 2, ..., n conveniently.
Given an integer k, Bobo chooses a subset of edges such that the vertices 1, 2, ..., k can reach each other via the chosen edges. He wants the chosen number of edges is minimized. Find out the number of ways to choose modulo (109+7).
Given an integer k, Bobo chooses a subset of edges such that the vertices 1, 2, ..., k can reach each other via the chosen edges. He wants the chosen number of edges is minimized. Find out the number of ways to choose modulo (109+7).
输入描述:
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains three integers n, m and k.
The i-th of the following m lines contains 2 integers ai and bi which denote the edge between vertices ai and bi.
输出描述:
For each test case, print an integer which denotes the result.
备注:
* 1 ≤ n ≤ 50
*
*
* 1 ≤ ai, bi ≤ n
* The number of test cases does not exceed 100.
* The number of test cases with n > 8 does not exceed 5.