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

#define int unsigned long long
#define NO return cout<<"NIE",0

const int N=2e5+5;

int n,m,rt;
vector<int>e[N];

int dep[N],mx[2][N];
int f[N],g[N],mn[2][N];

void getdep(int u,int fa){
    for(int v:e[u]){
        if(v==fa)continue;
        dep[v]=dep[u]+1;
        getdep(v,u);
        if(mx[0][v]+1>mx[0][u])
            mx[1][u]=mx[0][u],mx[0][u]=mx[0][v]+1;
        else mx[1][u]=max(mx[1][u],mx[0][v]+1);
    }
}

void getmx(int u,int fa){
    for(int v:e[u]){
        if(v==fa)continue;
        if(mx[0][v]+1==mx[0][u])
            if(mx[1][u]+1>mx[0][v])
                mx[1][v]=mx[0][v],mx[0][v]=mx[1][u]+1;
        getmx(v,u);
    }
}

void dfs(int u,int fa){
    f[u]=1;
    mn[1][u]=1e18;
    for(int v:e[u]){
        if(v==fa)continue;
        dfs(v,u);
        f[u]+=(f[v]<<1);
        g[u]+=g[v];
        if(mn[0][u]==0)mn[0][u]=f[v];
        else if(f[v]<mn[0][u])
            mn[1][u]=mn[0][u],mn[0][u]=f[v];
        else mn[1][u]=min(mn[1][u],f[v]);
    }
    g[u]+=mn[0][u];
}

void fds(int u,int fa){
    for(int v:e[u]){
        if(v==fa)continue;
        f[v]+=(f[u]-f[v]*2)*2;
        int val=g[u]-g[v];
        if(mn[0][u]==f[v])
            val-=mn[0][u],val+=mn[1][u];
        g[v]+=val;
        
        val=(f[u]-f[v]*2)*2;
        if(mn[0][v]==0)mn[0][v]=val;
        else if(val<mn[0][v])
            mn[1][v]=mn[0][v],mn[0][v]=val;
        else mn[1][v]=min(mn[1][v],val);

        fds(v,u);
    }
}

signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin>>n>>m;
    if(m>n-1)NO;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    for(int i=1;i<=n;i++)
        if(e[i].size()>3)NO;
    getdep(1,0),getmx(1,0);
    mx[0][0]=1e18;
    for(int i=1;i<=n;i++)
        if(mx[0][i]<mx[0][rt]&&e[i].size()<3)rt=i;
    if(mx[0][rt]>33)NO;
    dfs(rt,0),fds(rt,0);

    int ans=1e18;
    for(int i=1;i<=n;i++){
        if(e[i].size()==3)continue;
        if(e[i].size()==1){
            if(mx[0][i]>31)continue;
            ans=min(ans,g[i]);
        }
        else {
            if(mx[0][i]>30)continue;
            ans=min(ans,f[i]+g[i]);
        }
    }
    if(ans==1e18)NO;
    cout<<ans;

    return 0;
}