#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N = 2e5 + 5;
const ll inf = 1e18;
int n,m,d[N],vis[N];
vector<int>e[N];
bool check(int u,int fa){
	if(d[u] > 3) return 0;
	vis[u] = 1;
	bool fl = 1;
	for(auto v : e[u]){
		if(v == fa) continue;
		if(vis[v]) return 0;
		fl &= check(v,u);
		if(!fl) return 0;
	}
	return 1;
}
struct nd{
	ll k,b;
};
struct node{
	ll k,b;
	int dep[40];
};
map<int,node>f[N];
void dfs(int u,int fa){
	if(f[u].count(fa)) return;
	f[u][fa].dep[0] = 1;
	vector<nd>tmp;
	for(auto v : e[u]){
		if(v == fa) continue;
		dfs(v,u);
		for(int i = 0;i <= 34;++ i)
			f[u][fa].dep[i + 1] += f[v][u].dep[i];
		tmp.pb({f[v][u].k,f[v][u].b});
	}
	if(tmp.size() == 0) f[u][fa].k = 1,f[u][fa].b = 0;
	if(tmp.size() == 1) f[u][fa].k = 2 * tmp[0].k + 1,f[u][fa].b = tmp[0].b;
	if(tmp.size() == 2) f[u][fa].k = 2 * (tmp[0].k + tmp[1].k) + 1,f[u][fa].b = tmp[0].b + tmp[1].b + min(tmp[0].k,tmp[1].k);
	f[u][fa].k = min(f[u][fa].k,inf);
	f[u][fa].b = min(f[u][fa].b,inf);
}
int main(){
	cin >> n >> m;
	for(int i = 1;i <= m;++ i){
		int a,b;
		cin >> a >> b;
		e[a].pb(b);e[b].pb(a);
		d[a] ++;d[b] ++;
	}
	if(!check(1,0)) return cout << "NIE",0;
	ll ans = inf;
	for(int i = 1;i <= n;++ i)
		if(d[i] <= 2){
			dfs(i,0);
			if(d[i] == 1){
				if(f[i][0].dep[33]) continue;
				ans = min(ans,f[e[i][0]][i].k + f[e[i][0]][i].b);
			}
			else{
				if(f[i][0].dep[32]) continue;
				ans = min(ans,f[i][0].k + f[i][0].b);
			}
				
		}
	if(ans == inf) cout << "NIE";
	else cout << ans;
	return 0;
}