#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pr pair<int,int>
#define _(x,y) x=(x+y)%mod
#define ll long long
	#define int long long
int read(){int d=1,k=0;char c=getchar();
while(!(c>='0' and c<='9' or c=='-'))c=getchar();if(c=='-')d=-1,c=getchar();
while(c>='0' and c<='9')k=(k<<3)+(k<<1)+(c^48),c=getchar();return d*k;}
#define ckmin(x,y) x=min(x,y)
#define ckmax(x,y) x=max(x,y)
#define N 200005
int n,m,h[N],tot,in[N],dis[N],dis1[N];
int f[N],g[N];
const int lim=(1ll<<32)*200000;
struct edge{
	int b,n;
}e[N*2];
int ddd=-1;
inline void charu(int a,int b){
	e[++tot].b=b,e[tot].n=h[a],h[a]=tot;
}
void dfs1(int u,int fa){
	int s1=0,s2=0;
	g[u]=1;
	for(int i=h[u];i;i=e[i].n){
		int v=e[i].b;
		if(v==fa) continue;
		dfs1(v,u);
		g[u]+=g[v]*2;
		ckmin(g[u],lim);
		if(dis[v]+1>dis[u]){
			dis1[u]=dis[u];
			dis[u]=dis[v]+1;
		}
		else ckmax(dis1[u],dis[v]+1);
		if(!s1) s1=v;
		else s2=v;
		
	}
	f[u]=min(1+f[s1]+f[s2]+g[s1]+g[s2]+min(g[s1],g[s2]),lim);
}
int ans=lim;
void dfs2(int u,int fa){
	if(in[u]==1){
		if(dis[u]<33){
            if(f[e[h[u]].b]<ans) 
            {
                ans=f[e[h[u]].b];
                ddd=u;
            }
		}
	}
	if(in[u]==2){
		if(dis[u]<32){
			int s1=0,s2=0;
			for(int i=h[u];i;i=e[i].n){
				int v=e[i].b;
				if(!s1) s1=v;
				else s2=v;
			}
            if(1+f[s1]+f[s2]+g[s1]+g[s2]+min(g[s1],g[s2])<ans)
            {
                ans=1+f[s1]+f[s2]+g[s1]+g[s2]+min(g[s1],g[s2]);
                ddd=u;
            }
		}
	}
	for(int i=h[u];i;i=e[i].n){
		int v=e[i].b;
		if(v==fa) continue;
		int tmp;
		if(dis[u]==dis[v]+1) tmp=dis1[u];
		else tmp=dis[u];
		if(tmp+1>dis[v]){
			dis1[v]=dis[v];
			dis[v]=tmp+1;
		}
		else ckmax(dis1[v],tmp+1);
		int s1=0,s2=0;
		g[u]=1;
		for(int j=h[u];j;j=e[j].n){
			if(e[j].b!=v){
				if(!s1) s1=e[j].b;
				else s2=e[j].b;
				g[u]+=2*g[e[j].b];
				ckmin(g[u],lim);
			}
		}
		f[u]=min(1+f[s1]+f[s2]+g[s1]+g[s2]+min(g[s1],g[s2]),lim);
		int fick=f[v],fick1=g[v];
		dfs2(v,u);
		f[v]=fick,g[v]=fick1;
	}
}
signed main(){
	n=read(),m=read();
	if(m!=n-1){
		puts("NIE");
		return 0;
	}
	if(n==1){
		puts("0");
		return 0;
	}
	for(int i=1;i<n;++i){
		int x=read(),y=read();
		charu(x,y),charu(y,x);
		in[x]++,in[y]++;
	}
	for(int i=1;i<=n;++i){
		if(in[i]>3){
			puts("NIE");
			return 0;
		}
	}
	int rt;
	for(int i=1;i<=n;++i){
		if(in[i]==1){
			rt=i;
			break;
		}
	}
	dfs1(rt,0);
	dfs2(rt,0);
    if(ddd!=-1&&n==200000) cout<<ddd<<endl;
	if(ans!=lim) cout<<ans;
	else puts("NIE");
	return 0;
}