//utl
#include<bits/stdc++.h>
#define int long long
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;
int fr[N],to[N*2],nt[N*2],cnt;
int n,m;
int r[N];
int son[N][2];
bool vis[N];
bool sf;
int ts[N],f[N];
long long ans;
bool vis2[N];
void ct(int x,int y){
	nt[++cnt]=fr[x];
	fr[x]=cnt;
	to[cnt]=y;
	return ;
}
bool isson(int x,int y){
	return y==son[x][0]||y==son[x][1];
}//fa ->son
int wz(int x,int y){
	return y==son[x][1];
}//fa ->son
void dfs1(int x,int fa){
	vis[x]=1;
	for(int i=fr[x];i;i=nt[i]){
		if(to[i]==fa) continue;
		if(vis[to[i]]==0) dfs1(to[i],x);
		else sf=1;
	}
	return ;
}
void dfs2(int x,int fa){
	ts[x]=1;
	int tot=0;
	f[x]=fa;
	for(int i=fr[x];i;i=nt[i]){
		if(to[i]==fa) continue;
		dfs2(to[i],x);
		son[x][tot++]=to[i];
	}
	ts[x]=ts[son[x][1]]*2+ts[son[x][0]]*2+min(ts[son[x][1]],ts[son[x][0]])+1;
	return ;
}
void cg(int x){
	vis2[x]=1;
	if(r[x]==1){
		int y=to[fr[x]];
		ans=min(ans,ts[y]);
		ts[x]=1;
		for(int i=fr[x];i;i=nt[i]){
			if(vis2[to[i]]) continue;
			cg(to[i]);
		}
		return ;
	}
	if(r[x]==2){
		ts[x]=(ts[son[x][0]]+ts[f[x]])*2+min(ts[son[x][0]],ts[f[x]])+1;
		ans=min(ans,ts[x]);
		for(int i=fr[x];i;i=nt[i]){
			if(vis2[to[i]]) continue;
			ts[x]=ts[f[x]]*2+1;
			cg(to[i]);
		}
		ts[x]=ts[son[x][0]]*2+1;
		return ;
	}
	for(int i=fr[x];i;i=nt[i]){
		if(vis2[to[i]]) continue;
		int sw=wz(x,to[i]);
		ts[x]=ts[son[x][sw^1]]*2+ts[f[x]]*2+min(ts[f[x]],ts[son[x][sw^1]])+1;
		cg(to[i]);
	}
	ts[x]=ts[son[x][0]]*2+ts[son[x][1]]*2+min(ts[son[x][0]],ts[son[x][1]])+1;
	return ;
}
signed main(){
	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);
	}
	dfs1(1,0);
	if(sf==1){
		cout<<"NIE";
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(r[i]<3){
			dfs2(i,0);
			cg(i);
			break;
		}
	}
	if(ans<0) cout<<"NIE";
	else cout<<ans<<"\n";
	return 0;
}