#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define lowbit(x) (x&-x)
#define log(x) (31^__builtin_clz(x))
using namespace std;
vector<int>e[200005];
struct Data{
    int dep;
    ll sum,res,tot;
    ll out(){
        return sum+tot;
    }
};
Data operator+(Data a,Data b){
    return {max(a.dep,b.dep),a.sum+b.sum,a.res+b.res,a.tot+b.tot};
}
Data upd(Data now){
    now.dep++;
    now.sum=now.sum*2+1;
    now.res=now.res*2+1;
    return now;
}
vector<Data>dat[200005];
Data dfs1(int x,int f){
    Data now={0,0,0};
    vector<ll>s;
    for(int i=0;i<e[x].size();i++){
        int u=e[x][i];
        if(u==f)continue;
        now=now+(dat[x][i]=dfs1(u,x));
        s.push_back(dat[x][i].res);
    }
    now=upd(now);
    if(s.size()==2)now.tot+=min(s[0],s[1]);
    return now;
}
void dfs2(int x,int f,Data p){
    for(int i=0;i<e[x].size();i++){
        int u=e[x][i];
        if(u==f)dat[x][i]=p;
    }
    for(int i=0;i<e[x].size();i++){
        int u=e[x][i];
        if(u==f)continue;
        Data now={0,0,0};
        vector<ll>s;
        for(int j=0;j<e[x].size();j++){
            if(i==j)continue;
            now=now+dat[x][j];
            s.push_back(dat[x][j].res);
        }
        now=upd(now);
        if(s.size()==2)now.tot+=min(s[0],s[1]);
        dfs2(u,x,now);
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(e[i].size()>3){
            cout<<"NIE\n";
            return;
        }
        dat[i].resize(e[i].size());
    }
    if(m>n-1){
        cout<<"NIE\n";
        return;
    }
    dfs1(1,0);
    dfs2(1,0,{0,0,0});
    ll ans=1e18;
    for(int i=1;i<=n;i++){
        if(e[i].size()==1){
            if(dat[i][0].dep>31)continue;
            ans=min(ans,upd(dat[i][0]).out());
        }
        if(e[i].size()==2){
            if(dat[i][0].dep>31||dat[i][1].dep>31)continue;
            ans=min(ans,upd(dat[i][0]+dat[i][1]).out());
            if(dat[i][0].dep==1)ans=min(ans,upd(dat[i][1]).out());
            if(dat[i][1].dep==1)ans=min(ans,upd(dat[i][0]).out());
        }
        if(e[i].size()==3){
            if(dat[i][0].dep>31||dat[i][1].dep>31||dat[i][2].dep>31)continue;
            if(dat[i][0].dep==1)ans=min(ans,upd(dat[i][1]+dat[i][2]).out()+min(dat[i][1].res,dat[i][2].res));
            if(dat[i][1].dep==1)ans=min(ans,upd(dat[i][0]+dat[i][2]).out()+min(dat[i][0].res,dat[i][2].res));
            if(dat[i][2].dep==1)ans=min(ans,upd(dat[i][0]+dat[i][1]).out()+min(dat[i][0].res,dat[i][1].res));
        }
    }
    if(ans==1e18)cout<<"NIE\n";
    else cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)solve();
    return 0;
}