### No.95 Alice and Graph

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 34

ProblemId : 23 / 出題時の順位表

#### 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$$
$$\vdots$$
$$U_M$$ $$V_M$$

$$1 \leq N \leq 60$$, denoting the number of the nodes
$$0 \leq M \leq N(N-1)/2$$, denoting the number of the edges
$$0 \leq K \leq 15$$, denoting the number of moves
$$1 \leq U_k, V_k \leq N$$, denoting the edge connecting nodes $$U_k$$ and $$V_k$$, where $$U_k \neq 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

##### Sample 1
4 3 1
1 2
1 3
1 4
###### Output
7

Alice can move node $$2$$ or node $$3$$ or node $$4$$. Here node $$4$$ has $$2^{4-1}-1 = 7$$ coins.

##### Sample 2
5 4 4
3 4
4 1
1 5
5 2
###### Output
25

The graph is as follows: $$3-4-1-5-2$$.
The optimal sequence of moves of Alice is $$1 \to 5 \to 1 \to 4 \to 3$$.
Thus the answer will be $$(2^{5-1}-1) + (2^{4-1}-1) + (2^{3-1}-1) = 15 + 7 + 3 = 25.$$

##### Sample 3
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
###### Output
1036150

ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。