#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>#include <cmath>#include <vector>#include <queue>#include <set>#include <stack>#include <string>#include <map>#include <ctype.h>#include <time.h>#define abs(x) ((x)>=0?(x):-(x))#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define clr(x,y) memset(x,y,sizeof(x))#define CLR(x) x.clear()#define ph(x) push(x)#define pb(x) push_back(x)#define Len(x) x.length()#define SZ(x) x.size()#define PI acos(-1.0)#define sqr(x) ((x)*(x))#define MP(x,y) make_pair(x,y)#define EPS 1e-6#define FOR0(i,x) for(i=0;i<x;i++)#define FOR1(i,x) for(i=1;i<=x;i++)#define FOR(i,a,b) for(i=a;i<=b;i++)#define FORL0(i,a) for(i=a;i>=0;i--)#define FORL1(i,a) for(i=a;i>=1;i--)#define FORL(i,a,b)for(i=a;i>=b;i--)#define rush() int CC;for(scanf("%d",&CC);CC--;)#define Rush(n) while(scanf("%d",&n)!=-1)using namespace std;void RD(int &x){scanf("%d",&x);}void RD(i64 &x){scanf("%lld",&x);}void RD(u64 &x){scanf("%I64u",&x);}void RD(u32 &x){scanf("%u",&x);}void RD(double &x){scanf("%lf",&x);}void RD(int &x,int &y){scanf("%d%d",&x,&y);}void RD(i64 &x,i64 &y){scanf("%lld%lld",&x,&y);}void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}void RD(i64 &x,i64 &y,i64 &z){scanf("%lld%lld%lld",&x,&y,&z);}void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}void RD(char &x){x=getchar();}void RD(char *s){scanf("%s",s);}void RD(string &s){cin>>s;}void PR(int x) {printf("%dn",x);}void PR(int x,int y) {printf("%d %dn",x,y);}void PR(i64 x) {printf("%lldn",x);}void PR(i64 x,i64 y) {printf("%lld %lldn",x,y);}void PR(u32 x) {printf("%un",x);}void PR(u64 x) {printf("%llun",x);}void PR(double x) {printf("%.2lfn",x);}void PR(double x,double y) {printf("%.5lf %.5lfn",x,y);}void PR(char x) {printf("%cn",x);}void PR(char *x) {printf("%sn",x);}void PR(string x) {cout<<x<<endl;}const int mod=1000000007;const i64 inf=((i64)1)<<60;const double dinf=1000000000000000000.0;const int INF=1000000;const int N=1005;struct node{ int v,cap,next;};node edges[N*10];int head[N],e;int curedge[N],h[N],num[N],pre[N];int s,t;void add(int u,int v,int cap){ edges[e].v=v; edges[e].cap=cap; edges[e].next=head[u]; head[u]=e++;}void Add(int u,int v,int cap){ add(u,v,cap); add(v,u,0);}int Maxflow(int s,int t,int n){ clr(h,0); clr(num,0); int i; FOR0(i,n+1) curedge[i]=head[i]; int u=s,Min,k,x,ans=0; while(h[u]<n) { if(u==t) { Min=INF*100; for(i=s;i!=t;i=edges[curedge[i]].v) { x=curedge[i]; if(edges[x].cap<Min) { Min=edges[x].cap; k=i; } } ans+=Min; u=k; for(i=s;i!=t;i=edges[curedge[i]].v) { x=curedge[i]; edges[x].cap-=Min; edges[x^1].cap+=Min; } } for(i=curedge[u];i!=-1;i=edges[i].next) { if(edges[i].cap>0&&h[u]==h[edges[i].v]+1) { break; } } if(i!=-1) { curedge[u]=i; pre[edges[i].v]=u; u=edges[i].v; } else { if(--num[h[u]]==0) break; curedge[u]=head[u]; x=n; for(i=head[u];i!=-1;i=edges[i].next) { k=edges[i].v; if(edges[i].cap>0&&h[k]<x) x=h[k]; } h[u]=x+1; num[x+1]++; if(u!=s) u=pre[u]; } } return ans;}int n,m;int a[55][55];int visit[55];void DFS(int u){ visit[u]=1; int i,v; FOR1(i,n) if(a[u][i]&&!visit[i]) { DFS(i); }}int ok(){ clr(visit,0); DFS(1); int i; FOR1(i,n) if(!visit[i]) return 0; return 1;}int cal(int s,int t){ clr(head,-1); e=0; int i,j; FOR1(i,n) Add(i,i+n,1); FOR1(i,n) for(j=1;j<=n;j++) if(a[i][j]) { Add(i+n,j,INF); } return Maxflow(s+n,t,n+n+2);}int get(){ int x=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } return x;}int main(){ while(scanf("%d%d",&n,&m)!=-1) { if(m==0) { if(n==0) puts("0"); else if(n==1) puts("1"); else puts("0"); continue; } clr(a,0); int u,v,i; FOR0(i,m) { u=get(); v=get(); a[u+1][v+1]=a[v+1][u+1]=1; } if(!ok()) { puts("0"); continue; } int j; int ans=INF; FOR1(i,n) for(j=1;j<=n;j++) if(i!=j) { int x=cal(i,j); ans=min(ans,x); } if(ans==INF||ans==n-1) ans=n; PR(ans); }}
