Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

• There are exactly n - 1 roads left.
• It is possible to get from each junction to any other one.
• There are exactly k dead ends on the resulting map.

Two ways are considered different if there is a road that is closed in the first way, and is open in the second one.

Input

The first line contains three integers n, m and k (3 ≤ n ≤ 10, n - 1 ≤ m ≤ n·(n - 1) / 2, 2 ≤ k ≤ n - 1) which represent the number of junctions, roads and dead ends correspondingly. Then follow m lines each containing two different integers v1 and v2 (1 ≤ v1, v2 ≤ n, v1 ≠ v2) which represent the number of junctions connected by another road. There can be no more than one road between every pair of junctions. The junctions are numbered with integers from 1 to n. It is guaranteed that it is possible to get from each junction to any other one along the original roads.

Output

Print a single number — the required number of ways.

Examples
Input
3 3 21 22 31 3
Output
3
Input
4 6 21 22 33 44 11 32 4
Output
12
Input
4 6 31 22 33 44 11 32 4
Output
4