参考：https://blog.csdn.net/qq_34564984/article/details/53843777

可能背了假的板子……

对于每个灯建立方程：与它相邻的灯的开关次数的异或和为1

异或高斯消元，然后dfs，遇到*元就分两种情况走，答案取max，加上最优性剪枝

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

const int N=45;

int n,m,a[N][N],ans[N],mn=1e9,tot;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void gaosi()

{

	// for(int i=1;i<=n;i++)

	// {

		// int now=i;

		// for(int j=i+1;j<=n;j++)

			// if(abs(a[now][i])<abs(a[j][i]))

				// now=j;

		// for(int j=i;j<=n+1;j++)

			// swap(a[now][j],a[i][j]);

		// for(int j=i;j<=n+1;j++)

			// a[i][j]/=a[i][i];

		// for(int j=i+1;j<=n;j++)

		// {

			// for(int k=i+1;k<=n+1;k++)

				// a[j][k]^=(a[j][i]^a[i][k]);

			// a[j][i]=0;

		// }

	// }

	for(int i=1;i<=n;i++)

    {

        int j=i;

        while(j<=n&&!a[j][i])

			j++;

        if(j>n)

			continue;

        if(i!=j)

			for(int k=1;k<=n+1;k++)

				swap(a[i][k],a[j][k]);

        for(int j=1;j<=n;j++)

            if(i!=j&&a[j][i])

                for(int k=1;k<=n+1;k++)

                    a[j][k]^=a[i][k];

    }

}

void dfs(int u)

{

	if(tot>=mn)

		return;

	if(!u)

	{

		mn=tot;

		return;

	}

	if(a[u][u])

	{

		int t=a[u][n+1];

		for(int i=u+1;i<=n;i++)

			if(a[u][i])

				t^=ans[i];

		ans[u]=t;

		if(t)

			tot++;

		dfs(u-1);

		if(t)

			tot--;

	}

	else

	{

		tot++,ans[u]=1;

		dfs(u-1);

		tot--,ans[u]=0;

		dfs(u-1);

	}

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<=n;i++)

		a[i][i]=a[i][n+1]=1;

	for(int i=1;i<=m;i++)

	{

		int x=read(),y=read();

		a[x][y]=a[y][x]=1;

	}

	gaosi();

	dfs(n);

	printf("%d\n",mn);

	return 0;

}