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

using LL=long long;
const int N=2e5+10;
const int M=N*2;
#define int LL
int n,m;
const LL INF=4294967296;
int fa[N];
void init(int n) {
    for(int i=1;i<=n;i++)fa[i]=i;
}
int find(int x) {
    if(fa[x]==x)return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
void unionn(int x,int y) {
    fa[find(y)]=find(x);
}
int h[N],e[M],ne[M],idx;
void add(int a,int b) {
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int len;
int root1,root2;
int root;
int dep[N],f[N];
int d[N];
void dfs(int u,int fat) {
    dep[u]=dep[fat]+1;
    f[u]=fat;
    if(len<dep[u])len=dep[u],root=u;
    for(int i=h[u];i!=-1;i=ne[i]) {
        int v=e[i];
        if(v==fat)continue;
        dfs(v,u);
    }
}
LL val[N];
bool work(LL x) {
    set<LL>st;
    vector<int>vis(n+1,0);
    int u=root2;
    while(u!=root1) {
        val[u]=x;
        vis[u]=1;
        st.insert(x);
        if(x)x*=2;
        else x=1;
        u=f[u];
    }

    int flag=1;
    auto dfs2=[&](auto &self,int a,int fat)->void {
        if(!flag)return;
        for(int i=h[a];i!=-1;i=ne[i]) {
            int b=e[i];
            if(b==fat||vis[b])continue;
            vis[b]=1;
            if(st.find(val[a]/2)==st.end()) {
                val[b]=val[a]/2;
                st.insert(val[a]/2);
            }
            else if(st.find(val[a]*2)==st.end()) {
                val[b]=val[a]*2;
                st.insert(val[b]);
            }
            else if(st.find(val[a]*2+1)==st.end()){
                val[b]=val[a]*2+1;
                st.insert(val[b]);
            }
            else {
                flag=0;
                return;
            }
            self(self,b,a);
        }
    };

    u=root2;
    while(u!=root1) {
        dfs2(dfs2,u,0);
        u=f[u];
        if(!flag)return false;
    }
    return true;
}
void solve() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)h[i]=-1;
    idx=0;
    init(n);
    int sign=1;
    int cnt=0;
    for(int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        d[u]++,d[v]++;
        if(d[u]>3||d[v]>3)sign=0;
        add(u,v),add(v,u);
        if(find(u)==find(v)) {
            sign=0;
        }
        else unionn(u,v),cnt++;
    }
    if(cnt!=n-1)sign=0;
    if(!sign) {
        cout<<"NIE"<<"\n";
        return;
    }
    len=0;
    dfs(1,0);
    root1=root;
    memset(f,0,sizeof(f));
    memset(dep,0,sizeof(dep));
    len=0;
    dfs(root,0);
    root2=root;
    //cerr<<"root: "<<root1<<" "<<root2<<"\n";
    //cerr<<"fa: "<<fa[root2]<<"\n";
    LL ans=0;
    auto get_ans=[&]() {
        //cerr<<"val: ";
        for(int i=1;i<=n;i++) {
            if(val[i]>=INF||val[i]<0) {
                //if(n==200000)cout<<"aaa"<<"\n";
                return false;
            }
            ans+=val[i];
            //cerr<<val[i]<<" ";
        }
        return true;
        //cerr<<"\n";
    };
    if(work(0)&&get_ans()) {
        cout<<ans<<"\n";
    }
    else {
        if(work(1)&&get_ans()) {
            cout<<ans<<"\n";
        }
        else cout<<"NIE"<<"\n";
    }
}
/*
4 3
1 2
1 3
1 4

4 6
1 2
2 3
3 4
4 1
1 3
2 4

 */
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}