#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
#define int long long
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
const int mxn=6005;
pair<int,int> e[mxn];
vector<int> a[mxn];
int d[mxn],sum[mxn];
signed main()
{
	int n=read(),m=read(),i,x,y,mn=1e9,s;
	for(i=1;i<=m;i++)
		x=read(),y=read(),e[i]={x,y},
		a[x].push_back(y),
		a[y].push_back(x);
	for(i=1;i<=m;i++)
	{
		memset(d,-1,n+1<<3);
		memset(sum,0,n+1<<3);
		x=e[i].first,y=e[i].second;
		queue<int> q;
		q.push(x);
		sum[x]=1;
		while(q.size())
		{
			int f=q.front();
			q.pop();
			for(auto i:a[f])
				if((i!=x||f!=y)&&(i!=y||f!=x))
				{
					if(d[i]==-1)
						sum[i]=1,d[i]=d[f]+1,q.push(i);
					else if(d[i]==d[f]+1)
						sum[i]+=sum[f];
				}		
		}
		if(d[y]!=-1)
		{
			if(d[y]+1==mn) s+=sum[y];
			else if(d[y]+1<mn)
				mn=d[y]+1,s=sum[y];
		}
	}
	cout<<s/mn;
}