#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=2e5+5;
const ll inf=9e18;

int n,m;
pair<int,int> e[N];
vector<int> son[N];
int deg[N];
ll k[N],b[N],ans;
int u[N],v[N],w[N];
int dep[N],maxn[N],mexn[N];

void dfs1(int x,int fa){
    dep[x]=dep[fa]+1;
    k[x]=1;
    b[x]=0;
    for(auto y:son[x]){
        if(y==fa) continue;
        dfs1(y,x);
        if(v[x]) w[x]=y;
        else if(u[x]) v[x]=y;
        else u[x]=y;

        if(dep[y]>maxn[x]){
            mexn[x]=maxn[x];
            maxn[x]=dep[y];
        }else mexn[x]=dep[y];
    }

    if(k[u[x]]<k[v[x]]) swap(u[x],v[x]);
    if(k[u[x]]<k[w[x]]) swap(u[x],w[x]);
    
    int o=u[x],p=v[x],q=w[x];
    k[x]+=2ll*(k[o]+k[p]+k[q]);
    b[x]+=(b[o]+b[p]+b[q])+(k[p]+k[q]);
    // if(!(p+q)) b[x]+=1;
    // cout<<"? "<<x<<" "<<k[x]<<" "<<b[x]<<"\n";
    
}

void dfs2(int x,int fa,int depfa){
    // cout<<"? "<<x<<" "<<k[x]<<" "<<b[x]<<" "<<u[x]<<"\n";

    for(auto y:son[x]){
        if(y==fa) continue;

        ll old_k_x=k[x],old_b_x=b[x];

        k[x]-=2ll*k[y],b[x]-=b[y];
        if(y==u[x]){
            if(w[x])
                b[x]-=max(k[v[x]],k[w[x]]);
            else b[x]-=k[v[x]];
        }else{
            b[x]-=k[y];
        }
        dep[x]++;
        int len;
        if(maxn[x]==dep[y]) len=mexn[x];
        else len=maxn[x];
        len=max(len,maxn[y]-dep[y]);
        len=max(len,depfa+1);

        // cout<<"# "<<k[x]<<" "<<k[y]<<"\n";

        ll old_k_y=k[y],old_b_y=b[y];

        int o=x,p=u[y],q=v[y];
        if(k[o]<k[p]) swap(o,p);
        if(k[o]<k[q]) swap(o,q);
        k[y]=1+2ll*(k[o]+k[p]+k[q]);
        b[y]=(b[o]+b[p]+b[q])+(k[p]+k[q]);
        // if(!(p+q)) b[y]+=1;

        // cout<<"! "<<y<<" "<<k[y]<<" "<<b[y]<<"|"<<o<<" "<<k[o]<<" "<<b[o]<<"|";


        // cout<<ans<<"\n";
        
        
        if(deg[y]==1){
            if(len-1<32)
                ans=min(ans,k[o]+b[o]);
        }
        else if(deg[y]==2){
            if(len<32)
                ans=min(ans,k[y]+b[y]);
        }

        dfs2(y,x,depfa+1);

        
        k[y]=old_k_y,b[y]=old_b_y;
        k[x]=old_k_x,b[x]=old_b_x;
    }

}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        e[i]=make_pair(x,y);
    }

    if(m>=n){
        cout<<"NIE\n";
        return;
    }
    for(int i=1;i<n;i++){
        int x=e[i].first;
        int y=e[i].second;
        son[x].push_back(y);
        son[y].push_back(x);
        deg[x]++;
        deg[y]++;
    }

    for(int i=1;i<=n;i++){
        if(deg[i]>3){
            cout<<"NIE\n";
            return;
        }
    }

    dfs1(1,0);
    ans=inf;
    if(deg[1]==1){
        if(maxn[1]-2<32)
            ans=min(ans,k[u[1]]+b[u[1]]);
    }
    else if(deg[1]==2){
        if(maxn[1]-1<32)
            ans=min(ans,k[1]+b[1]);
    }

    dfs2(1,0,0);
    cout<<ans<<"\n";

}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n=1;
    // cin>>n;
    while(n--)solve();
    return 0;
}