#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(),vec.end()
#define umap __gnu_pbds::gp_hash_table
using ll = long long;
using i128 = __int128;
using db = double;
#define Emu Smile
using namespace std;

void chmax(auto &a, auto b) { if (a < b) a = b; }
void chmin(auto &a, auto b) { if (a > b) a = b; }
inline int lbt(int x) { return x & (-x); }

const int P = 1e9+7, B = 1000;
const ll inf = 1e16;

void no() {
	cout << "NIE\n";
}

struct Info {
	ll mind, addd, depd;
	Info():mind(0),addd(0),depd(0){}
	Info friend operator + (Info li,Info ri) {
		Info ret;
		ret.depd = max(li.depd, ri.depd) + 1;
		ret.mind = li.mind + ri.mind + li.addd + ri.addd + min(li.addd, ri.addd) + 1;
		ret.addd = (li.addd + ri.addd) * 2 + 1;
		return ret;
	}
};

void solve() {
	int n,m; cin >> n >> m;
	vector eg(n, vector<int>());
	for (int i = 0, x, y; i < m; ++i) {
		cin >> x >> y; x--, y--;
		eg[x].emplace_back(y), eg[y].emplace_back(x);
	}
	if (m > n-1) { return no(); }
	int root = 0;
	for (int i = 0; i < n; ++i) {
		if (sz(eg[i]) > 3) { return no(); }
		if (sz(eg[i]) <= 2) root = i;
	}
	if (!root) return no();
	vector<int> maxdep(n);
	{
		vector<int> tmp(n); int maxd = 0;
		auto dfs1 = [&](auto &self,int u,int fa) -> void {
			if (tmp[u] > tmp[maxd]) maxd = u;
			for (auto v : eg[u]) {
				if (fa == v) continue;
				tmp[v] = tmp[u] + 1;
				self(self, v, u);
			}
		};
		dfs1(dfs1, root, -1);
		auto dfs2 = [&](auto &self,int u,int fa) -> void {
			chmax(maxdep[u], tmp[u]);
			if (tmp[u] > tmp[maxd]) maxd = u;
			for (auto v : eg[u]) {
				if (fa == v) continue;
				tmp[v] = tmp[u] + 1;
				self(self, v, u);
			}
		};
		tmp.assign(n, 0);
		dfs2(dfs2, maxd, -1);
		tmp.assign(n, 0);
		dfs2(dfs2, maxd, -1);
	}
	root = -1;
	for (int i = 0; i < n; ++i) {
		if (sz(eg[i]) == 1) {
			if (maxdep[i] < 33) {
				root = i; break;
			}
		} else if (sz(eg[i]) == 2) {
			if (maxdep[i] < 32) {
				root = i; break;
			}
		}
	}
	if (root == -1) {
		return no();
	}
	vector<Info> f(n+1);
	{
		auto dfs = [&](auto &self,int u) -> void {
			for (auto v : eg[u]) {
				eg[v].erase(find(all(eg[v]), u));
				self(self, v);
			}
			if (sz(eg[u]) == 0) {
				f[u].mind = 1, f[u].addd = 1, f[u].depd = 0;
			} else if (sz(eg[u]) == 1) {
				int v = eg[u][0];
				f[u] = f[v] + Info();
			} else {
				int v1 = eg[u][0], v2 = eg[u][1];
				f[u] = f[v1] + f[v2];
			}
//			cout << u << " " << f[u].mind << " " << f[u].addd << '\n';
		};
		dfs(dfs, root);
	}
	ll ret = f[root].mind;
	if (sz(eg[root]) == 1) {
		int v = eg[root][0];
		chmin(ret, f[v].mind);
	}
	{
		vector<Info> g(n);
		auto check = [&](int x) {
			if (sz(eg[x]) == 0) {
				chmin(ret, g[x].mind);
			} else {
				chmin(ret, (f[x] + g[x]).mind);
			}
		};
		auto dfs = [&](auto &self,int u) -> void {
//			cout << u << " " << f[u].mind << " " << g[u].mind << " " << (f[u] + g[u]).mind << '\n';
			if (sz(eg[u]) == 1) {
				int v = eg[u][0];
				g[v] = g[u] + Info();
				check(v);
			} else if (sz(eg[u]) == 2){
				int v1 = eg[u][0], v2 = eg[u][1];
				g[v1] = g[u] + f[v2];
				check(v1);
				g[v2] = g[u] + f[v1];
				check(v2);
			}
			for (auto v : eg[u]) {
				if (sz(eg[v]) == 0) {
					if (maxdep[v] >= 33) continue;
				} else {
					if (maxdep[v] >= 32) continue;
				}
				self(self, v);
			}
		};
		dfs(dfs, root);
	}
	if (ret == inf) {
		return no();
	} else {
		cout << ret << '\n';
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);

//	init();

	cout << fixed << setprecision(10);

	int OuO = 1;
//	cin >> OuO;
	for (int piastic = 0; piastic < OuO; ++piastic) {
		solve();
	}
	return 0;
}