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

const int N = 4e5 + 5;
int n, m, du[N], ans = 4e18, rt;
vector<int> g[N];
bool vis[N], flag;
struct dpnode {
    int k, b;
    int dep;
} dp[N];

void merge(dpnode &x, dpnode y) { x = {y.k * 2 + 1, y.b * 2, y.dep + 1}; }
void merge(dpnode &x, dpnode y, dpnode z) {
    x.k = 1 + 2 * (y.k + z.k);
    x.b = 2 * (y.b + z.b) + min(y.k, z.k);
    x.dep = max(y.dep, z.dep) + 1;
}
void dfs(int x, int fa) {
    if (vis[x]) return (void)(flag = 1);
    vis[x] = 1;
    for (int y : g[x]) if (y ^ fa) dfs(y, x);
}
void dfs1(int x, int fa) {
    int cnt = 0, son[3];
    for (int y : g[x]) if (y ^ fa) dfs1(y, x), son[++cnt] = y;
    if (!cnt) dp[x] = {1, 0, 1};
    if (cnt == 1) merge(dp[x], dp[son[1]]);
    if (cnt == 2) merge(dp[x], dp[son[1]], dp[son[2]]);
}
void dfs2(int x, int fa, dpnode dpf) {
    int cnt = 0, son[3];
    for (int y : g[x]) if (y ^ fa) son[++cnt] = y;
    dpnode now;
    if (du[x] < 3) {
        if (cnt == 0) {
            if (dpf.dep <= 32)
            ans = min(ans, dpf.k + dpf.b);
        }
        if (cnt == 1) {
            merge(now, dpf, dp[son[1]]);
            if (now.dep <= 32)
            ans = min(ans, now.k + now.b);
        }
    }
    if (cnt == 2) {
        merge(now, dp[son[2]], dpf);
        dfs2(son[1], x, now);
        merge(now, dp[son[1]], dpf);
        dfs2(son[2], x, now);
    }
    merge(now, dpf);
    if (cnt == 1) dfs2(son[1], x, now);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    if (n == 1) {
        cout << "0\n";
        return 0;
    }
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        g[x].push_back(y), g[y].push_back(x);
        du[x]++, du[y]++;
    }
    dfs(1, 0);
    if (flag) {
        cout << "NIE\n";
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        if (du[i] > 3) {
            cout << "NIE\n";
            return 0;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (du[i] < 3) {
            dfs1(i, 0);
            rt = i;
            break;
        }
    }
    dfs2(rt, 0, {0, 0, 0});
    if (g[rt].size() == 1 && dp[g[rt][0]].dep <= 32) ans = min(ans, dp[g[rt][0]].k + dp[g[rt][0]].b);
    if (g[rt].size() == 2 && dp[rt].dep <= 32) ans = min(ans, dp[rt].k + dp[rt].b);
    if (ans == 4e18) return (cout << "NIE\n"), 0;
    cout << ans << '\n';
    return 0;
}