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

/* --------------- fast io --------------- */ // begin
namespace Fread {
	const int SIZE = 1 << 21;
	char buf[SIZE], *S, *T;
	inline char getchar() {
		if (S == T) {
			T = (S = buf) + fread(buf, 1, SIZE, stdin);
			if (S == T) return '\n';
		}
		return *S++;
	}
} // namespace Fread
namespace Fwrite {
	const int SIZE = 1 << 21;
	char buf[SIZE], *S = buf, *T = buf + SIZE;
	inline void flush() {
		fwrite(buf, 1, S - buf, stdout);
		S = buf;
	}
	inline void putchar(char c) {
		*S++ = c;
		if (S == T) flush();
	}
	struct NTR {
		~ NTR() { flush(); }
	} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
	template<typename T>
	Reader& operator >> (T& x) {
		char c = getchar();
		T f = 1;
		while (c < '0' || c > '9') {
			if (c == '-') f = -1;
			c = getchar();
		}
		x = 0;
		while (c >= '0' && c <= '9') {
			x = x * 10 + (c - '0');
			c = getchar();
		}
		x *= f;
		return *this;
	}
	Reader& operator >> (char& c) {
		c = getchar();
		while (c == ' ' || c == '\n') c = getchar();
		return *this;
	}
	Reader& operator >> (char* str) {
		int len = 0;
		char c = getchar();
		while (c == ' ' || c == '\n') c = getchar();
		while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows
			str[len++] = c;
			c = getchar();
		}
		str[len] = '\0';
		return *this;
	}
	Reader(){}
} cin;
const char endl = '\n';
struct Writer {
	template<typename T>
	Writer& operator << (T x) {
		if (x == 0) { putchar('0'); return *this; }
		if (x < 0) { putchar('-'); x = -x; }
		static int sta[45];
		int top = 0;
		while (x) { sta[++top] = x % 10; x /= 10; }
		while (top) { putchar(sta[top] + '0'); --top; }
		return *this;
	}
	Writer& operator << (char c) {
		putchar(c);
		return *this;
	}
	Writer& operator << (char* str) {
		int cur = 0;
		while (str[cur]) putchar(str[cur++]);
		return *this;
	}
	Writer& operator << (const char* str) {
		int cur = 0;
		while (str[cur]) putchar(str[cur++]);
		return *this;
	}
	Writer(){}
} cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end

#define int unsigned __int128
#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;
        int val=mx[0][u]+1;
        if(mx[0][v]+1==mx[0][u])val=mx[1][u]+1;
        if(val>mx[0][v])
            mx[1][v]=mx[0][v],mx[0][v]=val;
        else mx[1][v]=max(mx[1][v],val);
        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(){

    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]>31)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;
}