#include<bits/stdc++.h>
using namespace std;
using u64=unsigned long long;
int n,m,rt;u64 ans=-1ull;
struct N_{int d;u64 s1,s2;}f[200010],g[200010];
vector<int>G[200010];
inline N_ merge1(N_ x){
   return{x.d+1,x.s1*2+1,x.s2};
}
inline N_ merge2(N_ x,N_ y){
   return{max(x.d,y.d)+1,(x.s1+y.s1)*2+1,x.s2+y.s2+min(x.s1,y.s1)};
}
void dfs(int u,int fa){
   if(fa)G[u].erase(find(begin(G[u]),end(G[u]),fa));
   for(int v:G[u])dfs(v,u);
   if(G[u].empty())f[u]={0,1,0};
   else if(G[u].size()==1)f[u]=merge1(f[G[u][0]]);
   else f[u]=merge2(f[G[u][0]],f[G[u][1]]);
}
void dfs2(int u){
   if(G[u].size()==1){
      int v=G[u][0];
      g[v]=merge1(g[u]),dfs2(v);
   }else if(G[u].size()==2){
      int x=G[u][0],y=G[u][1];
      g[x]=merge2(g[u],f[y]),
      g[y]=merge2(g[u],f[x]);
      dfs2(x),dfs2(y);
   }
   if(u==rt){
      if(f[u].d<32)ans=min(ans,f[u].s2+f[u].s1);
   }else{
      if(G[u].empty()&&g[u].d<32)ans=min(ans,g[u].s2+g[u].s1);
      if(G[u].size()==1){
         N_ w=merge2(g[u],f[G[u][0]]);
         if(w.d<32)ans=min(ans,w.s1+w.s2);
      }
   }
}
int main(){
   scanf("%d%d",&n,&m);
   if(n==1)return puts("0"),0;
   if(m!=n-1)return puts("NIE"),0;
   for(int u,v;m--;){
      scanf("%d%d",&u,&v);
      G[u].push_back(v),G[v].push_back(u);
   }
   for(int i=1;i<=n;i++)if(G[i].size()==1)rt=i;
   dfs(rt,0),g[rt]={-1,0,0},dfs2(rt);
   if(ans!=-1ull)printf("%llu",ans);
   else printf("NIE");
   return 0;
}