問題文

Alice は誕生日プレゼントとして母親から無向グラフをもらいました。
そして Alice はいつものように、今はそのグラフを使ってゲームをしています。

グラフには \(1\) から \(N\) までの番号が付いた \(N\) 個の頂点があり、頂点 \(k\) には \(2^{k-1} - 1\) 枚のコインがあります。
ゲーム開始時、Alice は頂点 \(1\) にいて、\(2^{1-1}-1 = 0\) なので頂点 \(1\) にコインはありません。
その後、Alice は高々 \(K\) 回移動できます。
各移動では、Alice は辺を通って隣接する頂点へ行き、その頂点にあるコインを集めることができます。
Alice が集められるコインの枚数の最大値はいくつでしょうか？
なお、Alice は頂点 \(1\) に戻る必要はないことに注意してください。

入力

\(N\) \(M\) \(K\)
\(U_1\) \(V_1\)
\(U_2\) \(V_2\)
\(\vdots\)
\(U_M\) \(V_M\)

\(1 \leq N \leq 60\)：頂点数を表す
\(0 \leq M \leq N(N-1)/2\)：辺数を表す
\(0 \leq K \leq 15\)：移動回数を表す
\(1 \leq U_k, V_k \leq N\)：頂点 \(U_k\) と頂点 \(V_k\) を結ぶ辺を表す。ここで \(U_k \neq V_k\) である
どの頂点の組の間にも辺は高々 1 本しかありません。
グラフが連結であるとは仮定しないでください。

出力

答えを 1 行に出力してください。
出力の末尾には改行文字が 1 つ必要です。
答えは 32 ビット整数型に収まらない場合がありますが、64 ビット整数型には収まることに注意してください。

サンプル

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