No.95 Alice and Graph

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 34
作問者 : LayCurseLayCurse
2 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
Input
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
Input
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
Input
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
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。