全ての次数が \(2\) となるグラフの辺の本数は握手の補題より \(N\) 本です．

辺の本数が \(N\) であるような \(N\) 頂点のグラフは \(\binom{N(N-1)/2}{N} \) （\(N=8\) のとき \(3108105\)）通りあるので，そのようなグラフを全部調べることで，頂点の次数がすべて \(2\) であるようなグラフを列挙することが可能です．

import itertools
N, M = map(int, input().split())
G = [[0] * N for _ in range(N)]
for _ in range(M):
    u, v = map(lambda x: int(x) - 1, input().split())
    G[u][v] = G[v][u] = 1
edges = [(i, j) for i in range(N) for j in range(i + 1, N)]
ans = 1 << 30
for e in itertools.combinations(edges, N):
    deg = [0] * N
    for u, v in e:
        deg[u] += 1
        deg[v] += 1
    if all(d == 2 for d in deg):
        ans = min(ans, N + M - 2 * sum(G[u][v] for u, v in e))
print(ans)