//utl
#include<bits/stdc++.h>
#define int __int128
using namespace std;
inline int read(){
	int s=0,z=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')z=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=(s<<3)+(s<<1)+(c^48);
		c=getchar();
	}
	return s*z;
}
const int N = 2e5+5;
long long fr[N],to[N*2],nt[N*2],cnt;
long long n,m;
long long r[N];
long long  son[N][2];
bool vis[N];
bool sf;
int ts[N],f[N],rts[N];
long long deep[N];
int ans;
bool vis2[N];
int root;
void ct(long long x,long long y){
	nt[++cnt]=fr[x];
	fr[x]=cnt;
	to[cnt]=y;
	return ;
}
int wz(long long x,long long y){
	return y==son[x][1];
}//fa ->son
void dfs2(long long x,long long fa){
	int tot=0;
	f[x]=fa;
	rts[x]=1;
	deep[x]=1;
	for(int i=fr[x];i;i=nt[i]){
		if(to[i]==fa) continue;
		dfs2(to[i],x);
		rts[x]+=rts[to[i]]*2;
		son[x][tot++]=to[i];
		deep[x]=max(deep[x],deep[to[i]]+1);
	}
	ts[x]=ts[son[x][1]]+rts[son[x][1]]+ts[son[x][0]]+rts[son[x][0]]+min(rts[son[x][1]],rts[son[x][0]])+1;
	return ;
}
void write(int x){
	long long s1=x%10;
	if(x>=10)write(x/10);
	cout<<s1;
}
void dfs(int x,int fa){
	deep[x]=deep[fa]+1;
	for(int i=fr[x];i;i=nt[i]){
		if(to[i]==fa) continue;
		dfs(to[i],x);
	}
	return ;
}

void find_dep(int x,int fa){
	if(r[x]<3){
		deep[x]=max(deep[x],deep[fa]+1);
		if(deep[x]<32&&!root){
			root=x;
			return ;
		}
	}
	int ks[2],wks;
	ks[0]=ks[1]=0;
	int tot=0;
	for(int i=fr[x];i;i=nt[i]){
		if(to[i]==fa) continue;
		ks[++tot]=i;
	}
	for(int i=fr[x];i;i=nt[i]){
		if(to[i]==fa) continue;
		if(to[i]==ks[1]) wks=1;
		else wks=0;
		deep[x]=max(deep[fa],deep[wks^1])+1;
		find_dep(to[i],x);
	}
	deep[x]=max(deep[ks[0]],deep[ks[1]])+1;
	return ;
}
void cg(long long x){
	vis2[x]=1;
	if(r[x]==1){
		int y=to[fr[x]];
		if(deep[y]>32) return ;
		if(deep[y]<32)ans=min(ans,ts[y]);
		ts[x]=1;
		rts[x]=1;
		deep[x]=1;
		for(int i=fr[x];i;i=nt[i]){
			if(vis2[to[i]]) continue;
			cg(to[i]);
		}
		return ;
	}
	if(r[x]==2){
		if(f[x]!=0)rts[x]=1+(rts[son[x][0]]+rts[f[x]])*2,ts[x]=(ts[son[x][0]]+ts[f[x]])+rts[son[x][0]]+rts[f[x]]+min(rts[son[x][0]],rts[f[x]])+1,deep[x]=max(deep[son[x][0]],deep[f[x]])+1;
		else rts[x]=1+(rts[son[x][0]]+rts[son[x][1]])*2,ts[x]=(ts[son[x][0]]+ts[son[x][1]])+rts[son[x][0]]+rts[son[x][1]]+min(rts[son[x][0]],rts[son[x][1]])+1,deep[x]=max(deep[son[x][0]],deep[son[x][1]])+1;
		if(deep[x]>=32) return ;
		if(deep[x]<32)ans=min(ans,ts[x]);
		for(int i=fr[x];i;i=nt[i]){
			if(vis2[to[i]]) continue;
			int sw=wz(x,to[i]);
			rts[x]=1+(rts[son[x][sw^1]]+rts[f[x]])*2;
			deep[x]=max(deep[son[x][sw^1]],deep[f[x]])+1;
			ts[x]=ts[son[x][sw^1]]+rts[son[x][sw^1]]+ts[f[x]]+rts[f[x]]+min(rts[f[x]],rts[son[x][sw^1]])+1;
			cg(to[i]);
		}
		deep[x]=max(deep[son[x][0]],deep[son[x][1]])+1;
		rts[x]=1+(rts[son[x][0]]+rts[son[x][1]])*2;
		ts[x]=ts[son[x][0]]+rts[son[x][0]]+ts[son[x][1]]+rts[son[x][1]]+min(rts[son[x][1]],rts[son[x][0]])+1;
		return ;
	}
	for(int i=fr[x];i;i=nt[i]){
		if(vis2[to[i]]) continue;
		int sw=wz(x,to[i]);
		rts[x]=1+(rts[son[x][sw^1]]+rts[f[x]])*2;
		deep[x]=max(deep[son[x][sw^1]],deep[f[x]])+1;
		ts[x]=ts[son[x][sw^1]]+rts[son[x][sw^1]]+ts[f[x]]+rts[f[x]]+min(rts[f[x]],rts[son[x][sw^1]])+1;
		cg(to[i]);
	}
	deep[x]=max(deep[son[x][0]],deep[son[x][1]])+1;
	rts[x]=1+(rts[son[x][0]]+rts[son[x][1]])*2;
	ts[x]=ts[son[x][0]]+rts[son[x][0]]+ts[son[x][1]]+rts[son[x][1]]+min(rts[son[x][1]],rts[son[x][0]])+1;
	return ;
}
signed main(){
//	freopen("slt.in","r",stdin);
//	freopen("my.out","w",stdout);
	n=read(),m=read();
	ans=1e18;
	for(int x,y,i=1;i<=m;i++){
		x=read(),y=read();
		r[x]++;
		r[y]++;
		if(r[x]>3||r[y]>3){
			cout<<"NIE";
			return 0;
		}
		ct(x,y);
		ct(y,x);
	}
	if(m!=n-1){
		cout<<"NIE";
		return 0;
	}
	dfs(1,0);
	find_dep(1,0);
	if(root==0){
		cout<<"NIE";
		return 0;
	}
	dfs2(root,0);
	cg(root);
	if(n==200000){
		write(root);
		puts("");
		write(ts[root]);
		puts("");
	}
	write(ans);
	return 0;
}