#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,inf=(1<<32)*200000;
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++;
}

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

void dfs(int id,int f)
{
	vector<pll> pl;
	dep[id]=1;
	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]});
	}
	meg(id,pl);
}

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) meg(id,pl);
	int ans=inf;
	if(du[id]==2&&tp<=31) ans=min(ans,dp[id][0]+dp[id][1]);
	else if(du[id]==1&&tp<=32) ans=min(ans,pl[0].fi+pl[0].se);
	if(ans>=0&&ans<res) res=ans;
	
	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]);
		}
		meg(id,pl);
		DFS(j,id,dp[id][0],dp[id][1],tp+1);
	}
}

void solve() {
	cin>>n>>m;
	if(n==1)
	{
		cout<<"0\n";
		return;
	}
	if(m!=n-1) flag=0;
	memset(h,-1,sizeof h);
	int rt=1;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		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;
	if(flag)
	{
		res=inf;
		dfs(rt,-1),
		DFS(rt,-1,0,0,0);
	}
	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;
}
/*
*/