这个题正向思考很难，正难则反

考虑原图的补图，可以证明： 若满足题目要求，补图的每一个连通块都是完全图

$证明：$

在原图上，若 $a,b$ 有边，则对于任意一个点 $c$ ，使得 $a,c$ 和 $b,c$ 有至少有一个连了边。

在补图上的是逆命题：若 $a,b$ 没有边，则存在一个点，使得 $a,c$ 有边 或 $b,c$ 有边。

逆命题是假命题，那么逆否命题就是真命题：在补图上，若 $a,b$ 有边，则对于任意的一个点 $c$ ，到 $a$ 和 $b$ 一定只有 $2$ 条边或 $0$ 条边。

可等价转化为：补图的每一个连通块都是完全图

$证毕$

注意到 $N\le 16$ ，可以用状态压缩dp

考虑设 $f_S$ 表示：将集合 $S$ 里的点变成合法的所需的最少的步数

枚举每一个 $T$ 是 $S$ 的子集，使得将 $T$ 里的所有点变成一个完全图时的最小步数

你可以预处理 $C_S$ ，为将集合 $S$ 里的点变成完全图的步数

这样的话就有一个显然的转移方程：

代码很好写，剩下的注释在解释里：

#include<iostream>
#include<cstdio>

using namespace std;

inline int read(){
	int x=0; char c=getchar();
	while (c<'0' || c>'9'){
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x;
}

int n,m,f[1<<17],e[17][17],c[1<<17];

int main(){
	n=read(); m=read();
	for (int i=1;i<=m;i++){
		int a=read(), b=read();
		e[a][b]=e[b][a]=1;//你可以假装这是反图
	}
	for (int S=0;S<(1<<n);S++){//预处理出 C[S]
		for (int i=1;i<=n;i++){
			if (!(S&(1<<(i-1)))) continue;
			for (int j=i+1;j<=n;j++){
				if (S&(1<<(j-1))) c[S]+=e[i][j]; //连边 
				else c[S]+=(e[i][j]^1);            //删边 
			}
		}
	}
	for (int S=0;S<(1<<n);S++){
		f[S]=c[S];
		for (int T=S;T;T=(T-1)&S){
			f[S]=min(f[S], f[S^T]+c[T]);
		}
	}
	printf("%d",f[(1<<n)-1]);
	return 0;
}