#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 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 f2[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);
    }
}
void dfs3(int u,int fat) {
    f2[u]=fat;
    for(int i=h[u];i!=-1;i=ne[i]) {
        int v=e[i];
        if(v==fat)continue;
        dfs3(v,u);
    }
}
LL val[N];
bool work(LL x,int root1,int root2,int f[]) {
    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+1)==st.end()){
                val[b]=val[a]*2+1;
                st.insert(val[b]);
            }
            else if(st.find(val[a]*2)==st.end()) {
                val[b]=val[a]*2;
                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;
}

struct DSU {
    vector<int> fa, siz;

    DSU() {
    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        fa.resize(n);
        iota(fa.begin(), fa.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != fa[x]) {
            x = fa[x] = fa[fa[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        fa[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};
void solve() {
    cin>>n>>m;
    DSU dsu(n+1);
    for(int i=1;i<=n;i++)h[i]=-1;
    idx=0;
    int sign=1;
    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(dsu.same(u,v)) {
            sign=0;
        }
        else dsu.merge(u,v);
    }
    if(dsu.size(1)!=n)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;
    dfs3(root2,0);
    //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";
    };
    LL tmp=-1;
    if(work(0,root1,root2,f)&&get_ans()) {
        tmp==-1?tmp=ans:tmp=min(ans,tmp);
    }
    if(work(0,root2,root1,f2)&&get_ans()) {
        tmp==-1?tmp=ans:tmp=min(ans,tmp);
    }
    if(work(1,root1,root2,f)&&get_ans()) {
        tmp==-1?tmp=ans:tmp=min(ans,tmp);
    }
    if(work(1,root2,root1,f2)&&get_ans()) {
        tmp==-1?tmp=ans:tmp=min(ans,tmp);
    }
    if(tmp==-1)cout<<"NIE"<<"\n";
    else cout<<tmp<<"\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;
}