We denote by \(\lbrace 0, 1 \rbrace^N\) the set of all strings of lengths \(N\) consisting of \(0\) and \(1\).

Starting from an empty path \(A = ()\), we consider the process of appending elements to \(A\) one by one.
We will denote a state in the process by state \((S, v)\) with a string \(S = s_1s_2\ldots s_N \in \lbrace 0, 1 \rbrace^N\) defined below and the last element \(v\) of \(A\).

• For \(i = 1, 2, \ldots, N\),
  • if \(A\) has even number of \(i\)’s, then \(S_i = 0\);
  • if \(A\) has odd number of \(i\)’s, then \(S_i = 1\).

The state where \(A\) is empty is denoted by the state \(\epsilon\).

For example, when \(N = 3\) and \(A\) transitions as \(() \rightarrow (2) \rightarrow (2, 1) \rightarrow (2, 1, 2) \rightarrow (2, 1, 2, 3)\) in the process of appending elements, the corresponding transitions of elements are \(() \rightarrow (2) \rightarrow (2, 1) \rightarrow (2, 1, 2) \rightarrow (2, 1, 2, 3)\).

In general, for each state, the following transitions are possible:

• When we are in state \((S, v)\), we can append Vertex \(v\) to \(A\), so for any vertex \(u\) adjacent to Vertex \(v\), we can transition as \((S, v) \rightarrow (S_u, u)\), where \(S_u\) is a string \(S\) with the \(u\)-th character flipped.
• Since we can append any vertex to an empty path, from the state \(\epsilon\), we can transition as \(\epsilon \rightarrow (E_u, u)\), where \(E_u\) is a string in which the \(u\)-th character is \(1\) and the other are \(0\).

“The length of shortest good path with respect to \(S_{\mathrm{target}} \in \lbrace 0, 1 \rbrace^N\)” is “the minimum number of elements to be appended until it reaches to any of states \((S_{\mathrm{target}}, 1), (S_{\mathrm{target}}, 2), \ldots, (S_{\mathrm{target}}, N)\), starting from the state \(\epsilon\) where the path is empty.”

Thus, on a directed graph \(G\) where the vertices are all possible states, and for each vertex, there is a directed edge from the vertex to each vertex corresponding to the state that can be transitioned, “the length of the shortest good path with respect to \(S_{\mathrm{target}} \in \lbrace 0, 1 \rbrace^N\)” is equal to “the shortest distance (the number of edges on the shortest path) on \(G\) from the state \(\epsilon\) to (the nearest from \(\epsilon\) of) \((S_{\mathrm{target}}, 1), (S_{\mathrm{target}}, 2), \ldots, (S_{\mathrm{target}}, N)\).”

Therefore, by doing Breadth-First Search (BFS) on \(G\) starting from State \(\epsilon\), we can obtain “the length of the shortest good path with respect to \(S_{\mathrm{target}} \in \lbrace 0, 1 \rbrace^N\)” for all \(S_{\mathrm{target}} \in \lbrace 0, 1 \rbrace^N\) at once. By computing their sum, we can obtain the answer for the original problem. (Note that you may have to write an exceptional process for \(S_{\mathrm{target}} = 000\ldots0\), depending on implementation.)

Hence, the problem can be solved in a total of \(\mathrm{O}(N^2 \cdot 2^N)\) time.

The following is a sample code in 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;
}