#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define ll long long
#define qwq 500007 
inline int read(){
	char c=getchar();
	int x=0;int flag=0;
	for(;c<'0'||c>'9';c=getchar())flag|=(c=='-');
	for(;c<='9'&&c>='0';c=getchar())x=(x<<1)+(x<<3)+c-'0';
	if(flag)return -x;
	return x;
}
struct Edge{
	int a,b;
}e[qwq];
int n,m;
int cnte=-1;
int first[qwq],next_[qwq<<1],to[qwq<<1];
inline void add(int a,int b){
	++cnte;
	next_[cnte]=first[a];
	first[a]=cnte;
	to[cnte]=b;
	return ;
}
inline void add_e(int a,int b){
	add(a,b);
	add(b,a);
	return ;
}
int Flag;
int deg[qwq];
std::vector<int>edge[10007]; 
int tag[qwq];
int main(){
	cnte=-1;
	memset(first,-1,sizeof(first));
	n=read();m=read();
	for(int i=1;i<=m;++i){
		e[i].a=read(),e[i].b=read();
		add_e(e[i].a,e[i].b);
		++deg[e[i].a];++deg[e[i].b];
	}
	for(int i=1;i<=m;++i){
		if(deg[e[i].a]<deg[e[i].b]||(deg[e[i].a]==deg[e[i].b]&&e[i].a<e[i].b)){
			edge[e[i].a].push_back(e[i].b);
//			printf("add:%d->%d\n",e[i].a,e[i].b);
		}
	}
	for(int i=1;i<=n+n;++i){
		for(int j=first[i];j!=-1;j=next_[j]){
			int v=to[j];
			for(int k=0;k<edge[v].size();++k){
				int w=edge[v][k];
				if(w==i)continue;
				if(tag[w]){
					Flag=1;
					goto here;
				}
				tag[w]=1;
			}
		}
		for(int j=first[i];j!=-1;j=next_[j]){
			int v=to[j];
			for(int k=0;k<edge[v].size();++k){
				int w=edge[v][k];
				if(w==i)continue;
				tag[w]=0;
			}
		}
	}
	here:;
	if(Flag){
		printf("%d\n",2);
	}
	else {
		printf("%d\n",3);
	}
	return 0;
}