AT_abc244_f [ABC244F] Shortest Good Path

[problemUrl]: https://atcoder.jp/contests/abc244/tasks/abc244_f $ N $ 個の頂点と $ M $ 本の辺からなる単純（自己ループおよび多重辺を持たない）かつ連結な無向グラフが与えられます。 $ i\ =\ 1,\ 2,\ \ldots,\ M $ について、$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結びます。 下記の $ 2 $ つの条件をともに満たす整数列 $ (A_1,\ A_2,\ \ldots,\ A_k) $ を長さ $ k $ の**パス**と呼びます。 - すべての $ i\ =\ 1,\ 2,\ \dots,\ k $ について、$ 1\ \leq\ A_i\ \leq\ N $ 。 - すべての $ i\ =\ 1,\ 2,\ \ldots,\ k-1 $ について、頂点 $ A_i $ と頂点 $ A_{i+1} $ は辺で直接結ばれている。 空列も長さ $ 0 $ のパスとみなします。 $ S\ =\ s_1s_2\ldots\ s_N $ を $ 0 $ と $ 1 $ のみからなる長さ $ N $ の文字列とします。 パス $ A\ =\ (A_1,\ A_2,\ \ldots,\ A_k) $ が下記を満たすとき、パス $ A $ を $ S $ に関する**良いパス**と呼びます。 - すべての $ i\ =\ 1,\ 2,\ \ldots,\ N $ について、次を満たす。 - $ s_i\ =\ 0 $ ならば、$ A $ に含まれる $ i $ の個数は偶数である。 - $ s_i\ =\ 1 $ ならば、$ A $ に含まれる $ i $ の個数は奇数である。 $ S $ として考えられる文字列（すなわち、$ 0 $ と $ 1 $ のみからなる長さ $ N $ の文字列）は $ 2^N $ 個ありますが、そのすべてにわたる「 $ S $ に関する良いパスのうち最短のものの長さ」の総和を出力してください。 この問題の制約下において、$ 0 $ と $ 1 $ からなる長さ $ N $ のどのような文字列を $ S $ として選んでも、$ S $ に関する良いパスが少なくとも $ 1 $ つ存在することが示せます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 17 $ - $ N-1\ \leq\ M\ \leq\ \frac{N(N-1)}{2} $ - $ 1\ \leq\ u_i,\ v_i\ \leq\ N $ - 与えられるグラフは単純かつ連結 - 入力はすべて整数 ### Sample Explanation 1 \- $ S\ =\ 000 $ のとき、空列 $ () $ は $ S $ に関する最短の良いパスであり、その長さは $ 0 $ です。 - $ S\ =\ 100 $ のとき、$ (1) $ は $ S $ に関する最短の良いパスであり、その長さは $ 1 $ です。 - $ S\ =\ 010 $ のとき、$ (2) $ は $ S $ に関する最短の良いパスであり、その長さは $ 1 $ です。 - $ S\ =\ 110 $ のとき、$ (1,\ 2) $ は $ S $ に関する最短の良いパスであり、その長さは $ 2 $ です。 - $ S\ =\ 001 $ のとき、$ (3) $ は $ S $ に関する最短の良いパスであり、その長さは $ 1 $ です。 - $ S\ =\ 101 $ のとき、$ (1,\ 2,\ 3,\ 2) $ は $ S $ に関する最短の良いパスであり、その長さは $ 4 $ です。 - $ S\ =\ 011 $ のとき、$ (2,\ 3) $ は $ S $ に関する最短の良いパスであり、その長さは $ 2 $ です。 - $ S\ =\ 111 $ のとき、$ (1,\ 2,\ 3) $ は $ S $ に関する最短の良いパスであり、その長さは $ 3 $ です。 よって、求める答えは $ 0\ +\ 1\ +\ 1\ +\ 2\ +\ 1\ +\ 4\ +\ 2\ +\ 3\ =\ 14 $ です。