• 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 ≤ mn * (n - 1) / 2, 2 ≤ kn - 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, v2n, v1v2) 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.

## Sample Input 1

```3 3 2`
1 2
2 3
1 3```

`3`

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

`12`

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

`4`