- #include<iostream>
- #include<cstdlib>
- #include<cstdio>
- #include<cstring>
- #include<queue>
- #include<algorithm>
- #include<cmath>
- #include<map>
- #define N 50
- using namespace std;
- int n,m,ans=0x7ffffff;
- int a[N][N],ope[N];
- void dfs(int sum,int wz)
- {
- if(sum>=ans)return;
- if(wz==0)
- {
- ans=sum;return;
- }
- if(a[wz][wz])
- {
- int l=a[wz][n+1];
- for(int i=wz+1;i<=n;i++) if(a[wz][i]) l^=ope[i];
- if(l)
- {
- ope[wz]=1;
- sum++;
- }
- dfs(sum,wz-1);
- if(l)
- {
- ope[wz]=0;
- sum--;
- }
- }
- else
- {
- ope[wz]=1;sum++;dfs(sum,wz-1);
- ope[wz]=0;sum--;dfs(sum,wz-1);
- }
- }
- void gx()
- {
- for(int i=1;i<=n;i++)
- {
- int bj=i;
- while(bj<=n&&!a[bj][i])bj++;
- if(bj>n)continue;
- if(bj!=i)
- {
- for(int j=1;j<=n+1;j++)
- {
- swap(a[i][j],a[bj][j]);
- }
- }
- for(int j=1;j<=n;j++)
- {
- if(i==j||!a[j][i])continue;
- for(int k=1;k<=n+1;k++)
- a[j][k]^=a[i][k];
- }
- }
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;i++)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- a[x][y]=a[y][x]=1;
- }
- for(int i=1;i<=n;i++)
- a[i][i]=1,a[i][n+1]=1;
- gx();
- dfs(0,n);
- printf("%d\n",ans);
- return 0;
- }