#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];

void dfs1(int x,int fa){
    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(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])+2*(k[p]+k[q]);
    
}

void dfs2(int x,int fa){
    if(deg[x]==1) ans=min(ans,b[x]);
    else if(deg[x]==2) ans=min(ans,k[x]+b[x]);

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

        k[x]-=2ll*k[y],b[x]-=b[y];
        if(y!=u[x]) b[x]-=2*k[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);
        
        ll old_k=k[y],old_b=b[y];
        k[y]=1+2ll*(k[o]+k[p]+k[q]);
        b[y]=(b[o]+b[p]+b[q])+2ll*(k[p]+k[q]);

        dfs2(y,x);

        
        k[y]=old_k,b[y]=old_b;

        k[x]+=2ll*k[y],b[x]+=b[y];
        if(y!=u[x]) b[x]+=2*k[y];
    }

}

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;
    dfs2(1,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;
}