#include <cstdio>
#include <set>
#include <cstring>
#include <vector>
#define pb push_back
#define NMAX 100005
#define LMAX 300005
#define HMAX 25
#define pii pair<int,int>
#define f first
#define s second
#define mp make_pair
using namespace std;
int n,m,grd[HMAX],rez,val[NMAX],grad[NMAX];
vector <pii> A[NMAX];
struct muchie{int a,b;};
muchie B[LMAX];
char marc[HMAX][HMAX],viz[HMAX][HMAX];
set <pii> H;
char seen[LMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&x,&y);
		val[x]++; val[y]++;
		A[x].pb(mp(y,i));
		A[y].pb(mp(x,i));
		B[i].a=x; B[i].b=y;
	}
	for (i=1; i<=n; i++)
	{
		val[i]*=-1;
		H.insert(mp(val[i],i));
	}
}
void dfs(int nod,int root)
{
	viz[root][nod]=1;
	int i;
	for (i=1; i<=n; i++)
		if (!viz[root][i] && marc[nod][i])
			dfs(i,root);
}
inline int verif()
{
	int i,j;
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			if (viz[i][j] && viz[j][i])
				return 1;
	return 0;
}
inline int max(int x,int y)
{
	return x>y ? x : y;
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void solve1()
{
	int i,j,t,best;
	rez=NMAX;
	for (i=0; i<(1<<m); i++)
	{
		memset(grd,0,sizeof(grd));
		memset(marc,0,sizeof(marc));
		for (j=1; j<=m; j++)
			if (i & 1<<(j-1))
				marc[B[j].b][B[j].a]=1,grd[B[j].b]++;
			else
				marc[B[j].a][B[j].b]=1,grd[B[j].a]++;
		memset(viz,0,sizeof(viz));
		for (j=1; j<=n; j++)
			dfs(j,j);
		if (verif())
		{
			best=0;
			for (j=1; j<=n; j++)
				best=max(best,grd[j]);
			rez=min(rez,best);
		}
	}
}
void solve2()
{
	int i,j,nod,vec,edge;
	for (i=1; i<=n; i++)
	{
		nod=(*H.begin()).s;
		H.erase(mp(val[nod],nod));
		for (j=0; j<A[nod].size(); j++)
		{
			vec=A[nod][j].f; edge=A[nod][j].s;
			if (!seen[edge])
			{
				seen[edge]=1;
				grad[vec]++;
				H.erase(mp(val[vec],vec));
				val[vec]++;
				H.insert(mp(val[vec],vec));
			}
		}
	}
	for (i=1; i<=n; i++)
		rez=max(rez,grad[i]);
}
int main()
{
	freopen("dag.in","r",stdin);
	freopen("dag.out","w",stdout);
	read();
	if (m<=20)
	{
		solve1();
		printf("%d\n",rez);
		return 0;
	}
	solve2();
	printf("%d\n",rez);
	return 0;
}
