\(0\) と \(1\) のみからなる長さ \(N\) の文字列すべてからなる集合を \(\lbrace 0, 1 \rbrace^N\) で表します。

空のパス \(A = ()\) からはじめ、\(A\) の末尾に要素を \(1\) つずつ追加していくことを考えます。
その過程で生じる状態を、次で定義する \(S = s_1s_2\ldots s_N \in \lbrace 0, 1 \rbrace^N\) と、\(A\) の末尾要素 \(v\) を用いて状態 \((S, v)\) と表します。

• \(i = 1, 2, \ldots, N\) について、
  • \(A\) に含まれる \(i\) の個数が偶数のとき \(S_i = 0\)
  • \(A\) に含まれる \(i\) の個数が奇数のとき \(S_i = 1\)

ただし、\(A\) が空である初期状態は状態 \(\epsilon\) で表します。

例えば \(N=3\) とし、\(A\) に要素を \(1\) つずつ追加していく過程で \(A\) が \(() \rightarrow (2) \rightarrow (2, 1) \rightarrow (2, 1, 2) \rightarrow (2, 1, 2, 3)\) と変わるとき、 それに対応して状態は \(\epsilon \rightarrow (010, 2) \rightarrow (110, 1) \rightarrow (100, 2) \rightarrow (101, 3)\) と遷移します。

一般に、各状態からは次に述べる状態遷移が可能です。

• 状態 \((S, v)\) のとき、\(A\) の末尾には頂点 \(v\) に隣接する頂点を追加できるので、頂点 \(v\) に隣接する任意の頂点 \(u\) について、\((S, v) \rightarrow (S_u, u)\) と遷移できます。ここで、\(S_u\) は \(S\) の \(u\) 文字目を反転させて得られる文字列です。
• 空のパスには任意の頂点を追加できるので、状態 \(\epsilon\) からは任意の \(1 \leq u \leq N\) について、\(\epsilon \rightarrow (E_u, u)\) と遷移できます。ただし、\(E_u\) は \(u\) 文字目が \(1\) でそれ以外が \(0\) である文字列です。

「 \(S_{\mathrm{target}} \in \lbrace 0, 1 \rbrace^N\) に関する最短の良いパスの長さ」は、「パスが空の状態 \(\epsilon\) から始めて、状態 \((S_{\mathrm{target}}, 1), (S_{\mathrm{target}}, 2), \ldots, (S_{\mathrm{target}}, N)\) のいずれかに至るまでに追加する要素の個数の最小値」です。

よって、あり得るすべての状態を頂点とし、各頂点について、その頂点の状態から遷移可能なすべての状態の頂点へと有向辺を張った有向グラフ \(G\) を考えると、「 \(S_{\mathrm{target}} \in \lbrace 0, 1 \rbrace^N\) に関する最短の良いパスの長さ」は、「 \(G\) における、状態 \(\epsilon\) から \((S_{\mathrm{target}}, 1), (S_{\mathrm{target}}, 2), \ldots, (S_{\mathrm{target}}, N)\) （のうち最も \(\epsilon\) に近いもの）への最短距離（たどる辺の本数）」になります。

したがって、\(G\) 上で状態 \(\epsilon\) を始点とする幅優先探索を行うことで、すべての \(S_{\mathrm{target}} \in \lbrace 0, 1 \rbrace^N\) について「 \(S_{\mathrm{target}} \in \lbrace 0, 1 \rbrace^N\) に関する最短の良いパスの長さ」をまとめて求めることができ、それらの総和として本問題の答えが得られます。 （実装方法によっては、\(S_{\mathrm{target}} = 000\ldots0\) に対して例外的な処理が必要となることに注意してください。）

以上より、本問題を \(\mathrm{O}(N^2 \cdot 2^N)\) 時間で解くことができます。

C++ 言語による正解例を以下に記載します。

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
const int inf = 1000000000;

int n, m;
vector<int> G[20];
int dist[1<<17][17];

int main(void)
{
  cin >> n >> m;
  int u, v;
  for(int i = 1; i <= m; i++){
    cin >> u >> v;
    u--, v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  int N = 1<<n;
  for(int i = 0; i < N; i++) for(int j = 0; j < n; j++) dist[i][j] = inf;
  queue<pair<int, int>> Q;
  for(int i = 0; i < n; i++) dist[1<<i][i] = 1, Q.push({1<<i, i});

  while(Q.size()){
    int s = Q.front().first, v = Q.front().second; Q.pop();
    for(auto u : G[v]){
      int ns = s ^ (1<<u);
      if(dist[ns][u] < inf) continue;
      dist[ns][u] = dist[s][v] + 1;
      Q.push({ns, u});
    }
  }

  long long ans = 0;
  for(int i = 1; i < N; i++){
    int mn = inf;
    for(int j = 0; j < n; j++) mn = min(mn, dist[i][j]);
    ans += mn;
  }
  cout << ans << endl;

  return 0;
}