#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define lowbit(x) x&(-x)
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef pair<int,int> pir;
inline int read(){
	int x=0,f=1; char c=getchar();
	while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
	while(isdigit(c)){x=x*10+(c^48); c=getchar();}
	return x*f;
}
const int inf=1e9,N=4e2+5;
int n,m;
int head[N],cnt=1;
struct edge{int v,nxt,w;}p[N*2],q[N*2];
inline void add_edge(int u,int v,int w){
    p[++cnt]={v,head[u],w};
    head[u]=cnt;
    p[++cnt]={u,head[v],0};
    head[v]=cnt;
}
int S,T,du[N],vis[N],cur[N];
inline bool bfs(){
    queue<int> qu;
    qu.push(S);
    for(int i=1;i<=2*n;i++) vis[i]=du[i]=0;
    while(!qu.empty()){
        int x=qu.front();
        qu.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=q[i].nxt){
            int v=p[i].v;
            if(!q[i].w) continue;
            if(!vis[v]){
                du[v]=du[x]+1;
                qu.push(v);
            }
        }
    }
    return vis[T];
}
inline int dfs(int x,int flow){
    if(x==T) return flow;
    int num=0;
    for(int i=cur[x];i;i=q[i].nxt){
        cur[x]=i;//當前弧優化
        int v=q[i].v,w=q[i].w;
        if(du[v]==du[x]+1){
            int expand=dfs(v,min(flow,w));
            q[i].w-=expand;
            q[i^1].w+=expand;
            num+=expand;
            flow-=expand;
            if(!flow) return num;
        }
    }
    return num;
}
inline int Dinic(){
    for(int i=2;i<=cnt;i++) q[i]=p[i];
    int res=0;
    while(bfs()){
        res+=dfs(S,inf);
        memcpy(cur,head,sizeof(head));
    }
    return res;
}
int V[N];
vector<int> ed[N];
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) add_edge(i,i+n,1);
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        add_edge(u+n,v,inf);
        add_edge(v+n,u,inf);
        ed[u].push_back(v);
        ed[v].push_back(u);
    }
    for(auto v:ed[1]) V[v]=1;
    int ans=inf;
    for(int s=1;s<=n;s++){
        for(int i=1;i<=n;i++) V[i]=0;
        for(auto v:ed[s]) V[v]=1;
        V[s]=1;
        for(int t=1;t<=n;t++){
            if(V[t]) continue;
            S=n+s,T=t;
            ans=min(ans,Dinic());
        }
    }
	cout<<ans<<'\n';
}