Description

Alice was given an undirected graph by her mother as a birthday gift.
Then, as usual, Alice is now playing a game with the graph.

The graph has $N$ nodes, numbered from $1$ to $N$, and node $k$ has $2^{k-1}-1$ coins.
When the game starts, Alice is in node $1$, and there is no coin at node $1$, since $2^{1-1}-1=0$.
Then Alice will be allowed to move at most $K$ times.
At each move, Alice can go to an adjacent node through an edge, and collect the coins at the node.
The question is that what is the maximum number of coins can Alice collect?
Here please note that Alice does not have to go back to node $1$.

Input

$N$ $M$ $K$
$U_1$ $V_1$
$U_2$ $V_2$
$⋮$
$U_M$ $V_M$

$1\le N\le 60$, denoting the number of the nodes
$0\le M\le N(N-1)/2$, denoting the number of the edges
$0\le K\le 15$, denoting the number of moves
$1\le U_k,V_k\le N$, denoting the edge connecting nodes $U_k$ and $V_k$, where $U_k\ne V_k$
There is at most one edge between any pair of nodes.
Please do NOT assume that the graph is connected.

Output

Output the answer in one line.
One newline-character will be needed at the end of output.
Be careful that the answer may not fit a 32-bit integer type, but it will fit a 64-bit integer type.

Samples

4 3 1
1 2
1 3
1 4

7

5 4 4
3 4
4 1
1 5
5 2

25

20 21 15
8 16
2 11
7 5
6 8
17 8
4 17
15 20
13 14
5 11
2 12
19 18
11 18
10 19
3 7
9 8
20 2
3 19
17 15
3 2
17 11
1 9

1036150