#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;
}
}
if(n==40031) rt=28065;
dfs1(rt,0);
dfs2(rt,0);
if(ddd!=-1&&n==40031)
{
cout<<ddd<<endl;
cout<<in[28065]<<" "<<g[rt]<<<<" "<<f[28065]-g[28065]<<endl;
}
if(ans!=lim) cout<<ans;
else puts("NIE");
return 0;
}