For a simple undirected graph, the degree of every vertex is \(2\) if and only if every connected component is a cycle graph. Since the graph is simple, each cycle graph must have three or more vertices; thus, any connected component has at least three vertices.

By the constraints \(N \leq 8\), there are either one or two connected components in the final graph. Also note that, given a final graph, the minimum number of operations is easily counted by enumerating the edges that exists exactly one of either the initial or the final graph. We discuss by cases: when there are one connected component, and when there are two.

(1) if there is one connected component

It is sufficient to consider all permutations \((P_1, P_2, \ldots, P_N)\) of \((1, 2, \ldots, N)\) and consider the cycle graph of this order (where there are edges between \(P_i\) and \(P_{i + 1}\), with \(P_{N + 1} \coloneqq P_1\)). We may fix \(P_1 = 1\), but the small constraints allow us to enumerate all permutations.

(1) if there are two connected components

It is fast enough to try all divisions into two connected components and do the same thing as (1). On implementation, we may perform an exhaustive search using bitmasks, or enumerate permutations just as (1), split into the first \(d\) elements and last \((N-d)\) elements, and regard each portion as a cycle.

Sample code

#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';
}