by hansang:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=40;
LL f[N]; map<LL, LL> mp;
int main(){
    int n, m; LL ans=1e18; scanf("%d%d", &n, &m);
    f[1]=1ll; for(int i=2; i<=n; i++) f[i]=f[i-1]*2;
    for(int i=1; i<=m; i++){
        int x, y; scanf("%d%d", &x, &y);
        f[x]|=(1ll<<(y-1));
        f[y]|=(1ll<<(x-1));
    }
    for(int i=0; i<=(1ll<<(n/2))-1; i++){
        LL cnt=0, t=0;
        for(int j=1; j<=n/2; j++) if(i&(1ll<<(j-1))){
            t^=f[j];
            cnt++;
        }
        if(!mp.count(t)) mp[t]=cnt;
        else mp[t]=min(mp[t], cnt);
    }
    for(int i=0; i<=(1ll<<(n-n/2))-1; i++){
        LL cnt=0, t=0;
        for(int j=1; j<=n-n/2; j++) if(i&(1ll<<(j-1))){
            t^=f[n/2+j];
            cnt++;
        }
        if(mp.count(((1ll<<n)-1)^t)) ans=min(ans, cnt+mp[((1ll<<n)-1)^t]);
    }
    printf("%lld\n", ans);
    return 0;
}

by hansang:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=40;
LL f[N]; map<LL, LL> mp;
int main(){
	int n, m; LL ans=1e18; scanf("%d%d", &n, &m);
	f[1]=1ll; for(int i=2; i<=n; i++) f[i]=f[i-1]*2;
	for(int i=1; i<=m; i++){
		int x, y; scanf("%d%d", &x, &y);
		f[x]|=(1ll<<(y-1));
		f[y]|=(1ll<<(x-1));
	}
	for(int i=0; i<=(1ll<<(n/2))-1; i++){
		LL cnt=0, t=0;
		for(int j=1; j<=n/2; j++) if(i&(1ll<<(j-1))){
			t^=f[j];
			cnt++;
		}
		if(!mp.count(t)) mp[t]=cnt;
		else mp[t]=min(mp[t], cnt);
	}
	for(int i=0; i<=(1ll<<(n-n/2))-1; i++){
		LL cnt=0, t=0;
		for(int j=1; j<=n-n/2; j++) if(i&(1ll<<(j-1))){
			t^=f[n/2+j];
			cnt++;
		}
		if(mp.count(((1ll<<n)-1)^t)) ans=min(ans, cnt+mp[((1ll<<n)-1)^t]);
	}
	printf("%lld\n", ans);
	return 0;
}