#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;i++)
ll rd(){
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
#define d rd()
ll n,m;
vector<ll>e[200010];
ll deg[200010];
ll F[200010];
ll find(ll x){if(F[x]==x)return x;return F[x]=find(F[x]);}
void un(ll u,ll v){F[find(u)]=find(v);}
ll rt;
#define pb push_back
ll mx[200010],imx[200010],id[200010];
ll dep[200010];
ll far[200010];
void getd(ll u,ll fa){
    dep[u]=dep[fa]+1;mx[u]=imx[u]=0;id[u]=0;
    for(int i=0;i<e[u].size();i++){
        ll v=e[u][i];if(v==fa)continue;
        getd(v,u);if(mx[v]+1>mx[u]){
            imx[u]=mx[u];mx[u]=mx[v]+1;id[u]=v;
        }else if(mx[v]+1>=imx[u]){
            imx[u]=max(imx[u],mx[v]+1);
        }
    }
}
void getf(ll u,ll fa,ll mxl){
    if(u==rt){far[u]=1;
        for(int i=0;i<e[u].size();i++){
            ll v=e[u][i];if(v==fa)continue;
            getf(v,u,1);
        }
    }else{
        far[u]=mxl+1;
        for(int i=0;i<e[u].size();i++){
            ll v=e[u][i];if(v==fa)continue;
            if(v==id[u])getf(v,u,max(mxl+1,imx[u]+1));
            else getf(v,u,max(mxl+1,mx[u]+1));
        }
    }
}
struct node{ll a,b;}f[200010];
node merge(node a,node b){
    return {(a.a+b.a)*2+1,min(a.a,b.a)+a.b+b.b};
}
void pre(ll u,ll fa){
    f[u]={1,0};node x={0,0},y={0,0};
    for(int i=0;i<e[u].size();i++){
        ll v=e[u][i];if(v==fa)continue;
        pre(v,u);if(x.a==0)x=f[v];else y=f[v];
    }f[u]=merge(x,y);
}
ll res=0x3f3f3f3f3f3f3f3f;
void dfs(ll u,ll fa,node z){
    // cout<<u<<" "<<fa<<endl;
    if(deg[u]==1){
        if((u==rt&&mx[u]<=33)){
            res=min(res,((f[u].a-1)/2+f[u].b));
        }else if(u!=rt&&far[u]<=33){
            res=min(res,z.a+z.b);
        }
        if(u==rt)dfs(e[u][0],u,{1,0});
        return;
    }else if(deg[u]==2){
        if(max(far[u],mx[u])<=32){
            node x=z,y;
            for(int i=0;i<e[u].size();i++){
                ll v=e[u][i];if(v==fa)continue;y=f[v];
            }node t=merge(x,y);
            res=min(res,t.a+t.b);
        }
        for(int i=0;i<e[u].size();i++){
            ll v=e[u][i];if(v==fa)continue;
            dfs(v,u,merge(z,{0,0}));
        }return;
    }node x={0,0},y={0,0};
    ll ix=0,iy=0;
    for(int i=0;i<e[u].size();i++){
        ll v=e[u][i];if(v==fa)continue;
        if(ix==0)x=f[v],ix=v;
        else y=f[v],iy=v;
    }dfs(ix,u,merge(z,y));
    dfs(iy,u,merge(z,x));
}
int main(){bool flg=1;
    n=d,m=d;f(i,1,n)F[i]=i;
    if(m!=n-1)flg=0;f(i,1,m){
        ll u=d,v=d;
        e[u].pb(v),e[v].pb(u);
        deg[u]++;deg[v]++;
        if(deg[u]>=4||deg[v]>=4)flg=0;
        if(find(u)==find(v))flg=0;
        un(u,v);
    }if(!flg){puts("NIE");return 0;}
    if(n==1){puts("0");return 0;}
    f(i,1,n)if(deg[i]==1){rt=i;break;}
    getd(rt,0);getf(rt,0,0);
    f(i,1,n)if(max(mx[i],far[i]+1)<=32+(deg[i]==1))flg=0;
    if(flg){puts("NIE");return 0;}
    // f(i,1,n)cout<<i<<" "<<dep[i]<<" "<<mx[i]<<" "<<imx[i]<<" "<<far[i]<<endl;
    pre(rt,0);
    // f(i,1,n)cout<<f[i].a<<" "<<f[i].b<<endl;
    dfs(rt,0,{0,0});
    if(res==0x3f3f3f3f3f3f3f3f)puts("NIE");
    else cout<<res<<endl;
    return 0;
}
/*
7 6
1 2
2 3
2 4
4 5
4 6
5 7
*/