本意是想学高斯消元，然后一顿乱搞之后学到了一个神奇的搜索方式叫做折半搜索。
qwq
就是我先dfs前二分之n个点，然后再dfs后二分之n个点。
然后我dfs后二分之n个点的时候判断一下第一次dfs有没有搜到互补的状态（就是当前状态能不能跟之前搜到过的一个状态异或起来变成(1<<n)-1，即所有灯都开着）
如果能就看看能不能更新答案。
然后快的飞起qwq
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<map>
#define maxn 37
#define maxs (1<<14)
using namespace std;
map<long long,int> sta,stb;
inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} int n,m;
long long chan[maxn];
long long Max;
long long cnt;
int ans=0x7fffffff; void dfs(int x,long long state,int num){
cnt++;
if(sta.count(state)) sta[state]=min(sta[state],num);
else sta[state]=num;
if(x==(n>>)+) return;
long long now=state^chan[x];
dfs(x+,state,num);
dfs(x+,now,num+);
} void dfs2(int x,long long state,int num){
cnt++;
if(stb.count(state)) stb[state]=min(stb[state],num);
else stb[state]=num;
if(sta.count(Max^state)) ans=min(ans,sta[Max^state]+stb[state]);
if(x==n+) return;
long long now=state^chan[x];
dfs2(x+,state,num);
dfs2(x+,now,num+);
} int main(){
n=read(),m=read();
Max=(1LL<<n)-;
for(int i=;i<=m;++i){
long long x=read(),y=read();
chan[x]|=(1LL<<(y-));
chan[y]|=(1LL<<(x-));
}
for(long long i=;i<=n;++i) chan[i]|=(1LL<<(i-));
dfs(,,);
dfs2((n>>)+,,);
printf("%d",ans);
return ;
}