//Adrian Panaete 100 puncte
//Explicatie: 
//Aplic Greedy orientand mereu nodul de grad minim disponibil spre vecini.
//La fiecare nod eliminat gradul vecinilor neprelucrati se decrementeaza.
//Daca nodul prelucrat are gradul (eventual modificat de eliminari)
//  mai mare decat solutia atunci actualizez solutia.
//Complexitatea este ( M + N ) log N 
//Folosesc min-heap pentru a accesa rapid nodul ce cel mai mic grad disponibil.
//Nu sunt 100% sigur daca e corect rationamemntul !!!
#include<cstdio>
#include<vector>
#define E 300001
#define V 100001
using namespace std;
vector<int> e[V];
int ce,N,M,i,n,m,sol,x[E],y[E],v[E],g[V],h[V],p[V];
void read(),solve(),hu(int),hd(int);
bool grad(int,int);
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("dag.in","r",stdin);
	freopen("dag.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(i=1;i<=M;i++)
	{
		scanf("%d%d",&x[i],&y[i]);//memorez muchiile
		e[x[i]].push_back(i);//memorez muchia incidenta  unui capat
		e[y[i]].push_back(i);//memorez muchia incidenta altui capat
	}
}
void solve()
{
	vector<int>::iterator it;
	
	//formez min-heap al nodurilor ordonate dupa grad
	for(i=1;i<=N;i++)
	{
		g[i]=e[i].size();//citesc gradul
		h[i]=p[i]=i;//memorez nodul in heap si ii retin pozitia
		hu(i);//operatiunea heap_up ( urca nod spre radacina heap )
	}
	for(;N;)
	{
		n=h[1];v[n]=1;//aleg nodul din varful heap-ului si il vizitez
		sol=sol>g[n]?sol:g[n];g[n]=0;//actualizez solutia
		h[1]=h[N];p[h[1]]=1;N--;//elimin nodul din heap inlocuind varful cu ultimul
		hd(1);//si aplicand heap_down din varf
		for(it=e[n].begin();it!=e[n].end();it++)//parcurg vecinii
		{
			m=x[*it]+y[*it]-n;//determin vecinul
			if(v[m])continue;//daca e vizitat s-a prelucrat deja
			g[m]--;//duc muchie din nod curent in nodul vecin
			hu(p[m]);//deoarece vecinului i-a scazut gradul il ridic in heap
		}
	}
	printf("%d\n",sol);
	
}
void hu(int F)
{
	for(int T=F>>1;T;F>>=1,T>>=1)
	{
		if(g[h[T]]<=g[h[F]])return;
		h[T]^=h[F]^=h[T]^=h[F];
		p[h[T]]=T;p[h[F]]=F;
	}
}
void hd(int T)
{
	for(int F=T<<1;;)
	{
		
		if(F>N)return;
		if(F<N&&g[h[F]]>g[h[F+1]])F++;
		if(g[h[T]]<g[h[F]])return;
		h[T]^=h[F]^=h[T]^=h[F];
		p[h[T]]=T;p[h[F]]=F;T=F;F<<=1;
	}
}


