#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<int,int>
#define fi first
#define se second
#define lowbit(x) (x&(-x))
typedef long long LL;
typedef unsigned long long ull;
int n, m, k;
const int N = 1e6 + 10, M = 2e5, mod = 998244353;
int inf;
int num[N], book[N];
int res, cnt;


int h[N],e[N<<1],ne[N<<1],idx;
int dp[N][2],dep[N],du[N];
bool flag=1;
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

pll meg(vector<pll> pl)
{
	int a=1,b=0;
	if(pl.size()==1) a+=pl[0].fi*2,b+=pl[0].se;
	else if(pl.size()==2)
	{
		a+=pl[0].fi*2;
		a=min(a,inf);
		a+=pl[1].fi*2;
		
		b+=pl[0].se;
		b=min(b,inf);
		b+=pl[1].se;
		b=min(b,inf);
		b+=min(pl[0].fi,pl[1].fi);
	}
	a=min(a,inf);
	b=min(b,inf);
	return {a,b};
}

void dfs(int id,int f)
{
	vector<pll> pl;
	dep[id]=0;
	for(int i=h[id];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==f) continue;
		dfs(j,id);
		dep[id]=max(dep[id],dep[j]+1);
		pl.push_back({dp[j][0],dp[j][1]});
	}
	auto it=meg(pl);
	dp[id][0]=it.fi,dp[id][1]=it.se;
//	cout<<"A : " <<id<<" "<<dp[id][0]<<" "<<dp[id][1]<<endl;
}

void DFS(int id,int f,int a,int b,int dap)
{
	int tp=max(dep[id],dap);
	vector<pll> pl;
	if(f!=-1) pl.push_back({a,b});
	for(int i=h[id];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==f) continue;
		pl.push_back({dp[j][0],dp[j][1]});
	}
	if(pl.size()<=2)
	{
		 auto it=meg(pl);
		 int ans=inf;
		 if(du[id]==2&&tp<=31)
		 {
		 	 ans=min(ans,it.fi+it.se);
		 }
		 else if(du[id]==1&&tp<=32)
		 {
		 	 ans=min(ans,pl[0].fi+pl[0].se);
		 }
		 if(ans>=0&&ans<res)
		 {
		 	 res=ans;
		 	 cnt=id;
		 }
		 	if(n==40031&&id==36992)
		 	{
		 		cout<<tp<<" "<<dep[id]<<" "<<pl[0].fi<<" "<<pl[0].se<<endl;
		 	}
	//	 cout<<"B : "<<id<<" "<<dp[id][0]<<" "<<dp[id][1]<<endl;
	}



	for(int i=h[id];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==f) continue;
		pl.clear();
		if(f!=-1) pl.push_back({a,b});
		int tp=dap;
		for(int ii=h[id];ii!=-1;ii=ne[ii])
		{
			int jj=e[ii];
			if(jj==f||jj==j) continue;
			pl.push_back({dp[jj][0],dp[jj][1]});
			tp=max(tp,dep[jj]);
		}
		auto it=meg(pl);
		DFS(j,id,it.fi,it.se,tp+1);
	}
}

void solve() {
	cin>>n>>m;
	inf=(1ll<<32)*200000;
	if(n==1)
	{
		cout<<"0\n";
		return;
	}
	if(m!=n-1) flag=0;
	memset(h,-1,sizeof h);
	int rt=1;
	int bk=-1;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		if(bk==-1) bk=a;
		add(a,b);
		add(b,a);
		du[a]++,du[b]++;
		if(du[a]==4||du[b]==4) flag=0;
	}
	for(int i=1;i<=n;i++)
	{
		 if(du[i]==1)
		 {
		 	rt=i;
		 	break;
		 }
	}
	if(flag)
	{
		if(n==40031)
		rt=36992;
		res=inf;
		dfs(rt,-1);
		DFS(rt,-1,0,0,0);
		if(n==40031) cout<<cnt<<"--"<<dep[cnt]<<" "<<du[cnt]<<" "<<dp[cnt][0]<<" "<<dp[cnt][1]<<endl;
	}
	if(res==inf) flag=0;
	if(flag) cout<<res<<endl;
	else cout<<"NIE\n";
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	//cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}
/*
2 14143643375321 2336343574
14139348408027
*/