単純無向グラフのすべての頂点の次数が \(2\) であることは、すべての連結成分がサイクルグラフとなっていることと同値です。また、グラフがら単純であることから、サイクルグラフの頂点数は \(3\) 以上、すなわち各連結成分の頂点数は \(3\) 以上です。

制約 \(N \leq 8\) から、連結成分の数は \(1\) または \(2\) となります。また、最終的なグラフを固定したときの操作回数の最小値は、はじめのグラフと最終的なグラフの一方のみに存在する辺の個数を数えれば容易に求められることに注意しておきます。したがって、最終的に考えられるすべてのグラフが列挙できればよいです。連結成分の数が \(1\) つのときと \(2\) つのときのそれぞれについて考えます。

(1) 連結成分の数が \(1\) つのとき

順列全探索により \((1, 2, \ldots, N)\) のすべての並べ替え \((P_1, P_2, \ldots, P_N)\) についてこれらをサイクル状に並べた（すなわち、\(P_{N + 1} \coloneqq P_1\) として \(P_i\) と \(P_{i + 1}\) を結んだ）グラフを考えればよいです。順列は \(P_1 = 1\) であるもののみ考えればよいですが、制約が十分小さいのですべての順列を考えても十分高速です。

(2) 連結成分の数が \(2\) つのとき

\(2\) つの連結成分への分割方法をすべて試し、それぞれについて (1) と同じことを行えば十分高速です。実装の際は bit 全探索などをしてもよいですし、(1) と同様の順列全探索をして、前 \(d\) 個と後ろ \(N - d\) 個に分けてそれぞれを (1) と同様に定めるサイクルとしても十分高速です。

実装例

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
	int n, m;
	cin >> n >> m;
	vector f(n, vector<bool>(n));
	rep(i, m) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		if (u > v) swap(u, v);
		f[u][v] = true;
	}
	int ans = 100;
	vector<int> a(n);
	rep(i, n) a[i] = i;
	do {
		// cycle * 1
		vector g(n, vector<bool>(n));
		rep(i, n) {
			int u = a[i], v = a[(i + 1) % n];
			if (u > v) swap(u, v);
			g[u][v] = true;
		}
		int c0 = 0;
		rep(i, n) rep(j, n) if (f[i][j] != g[i][j]) c0++;
		if (c0 < ans) ans = c0;

		// cycle * 2
		for (int d = 3; d <= n - 3; d++) {
			vector h(n, vector<bool>(n));
			rep(i, d) {
				int u = a[i], v = a[(i + 1) % d];
				if (u > v) swap(u, v);
				h[u][v] = true;
			}
			rep(i, n - d) {
				int u = a[i + d], v = a[(i + 1) % (n - d) + d];
				if (u > v) swap(u, v);
				h[u][v] = true;
			}
			int c1 = 0;
			rep(i, n) rep(j, n) if (f[i][j] != h[i][j]) c1++;
			if (c1 < ans) ans = c1;
		}
	} while (next_permutation(a.begin(), a.end()));

	cout << ans << '\n';
}