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

const int N = 2e5 + 5;
const ll inf = 9e18;

int n, m;
pair<int, int> e[N];
vector<int> son[N];
int deg[N];
ll k[N], b[N], ans;
int u[N], v[N], w[N];
int dep[N], maxn[N], mexn[N], dia;

void dfs1(int x, int fa) {
    dep[x] = dep[fa] + 1;
    k[x] = 1;
    b[x] = 0;
    maxn[x] = mexn[x] = dep[x];
    for (auto y : son[x]) {
        if (y == fa)
            continue;
        dfs1(y, x);
        if (v[x])
            w[x] = y;
        else if (u[x])
            v[x] = y;
        else
            u[x] = y;

        if (maxn[y] >= maxn[x]) {
            mexn[x] = maxn[x];
            maxn[x] = maxn[y];
        } else if (maxn[y] >= mexn[x])
            mexn[x] = maxn[y];
    }
    dia = max(dia, maxn[x] - dep[x] + mexn[x] - dep[x] + 1);

    if (k[u[x]] < k[v[x]])
        swap(u[x], v[x]);
    if (k[u[x]] < k[w[x]])
        swap(u[x], w[x]);
    int o = u[x], p = v[x], q = w[x];
    k[x] += 2ll * (k[o] + k[p] + k[q]);
    b[x] += (b[o] + b[p] + b[q]) + (k[p] + k[q]);
    // cout<<"? "<<x<<" "<<k[x]<<" "<<b[x]<<"\n";
}

void calc(int x, int y) {
    int u = 0, v = 0;
    for (auto z : son[x]) {
        if (z == y)
            continue;
        if (u)
            v = z;
        else
            u = z;
    }
    k[x] = 1 + 2ll * (k[u] + k[v]);
    b[x] = (b[u] + b[v]) + min(k[u], k[v]);
}

void dfs2(int x, int fa, int depfa) {
    // cout<<"? "<<x<<" "<<k[x]<<" "<<b[x]<<" "<<u[x]<<"\n";

    for (auto y : son[x]) {
        if (y == fa)
            continue;

        ll old_k_x = k[x], old_b_x = b[x];
        calc(x, y);

        int len = 0;
        if (maxn[x] == maxn[y])
            len = mexn[x];
        else
            len = maxn[x];
        len = len - dep[x] + 1;
        len = max(len, depfa + 1);

        ll old_k_y = k[y], old_b_y = b[y];
        // int o = x, p = u[y], q = v[y];
        // if (k[o] < k[p])
        //     swap(o, p);
        // if (k[o] < k[q])
        //     swap(o, q);
        // k[y] = 1 + 2ll * (k[o] + k[p] + k[q]);
        // b[y] = (b[o] + b[p] + b[q]) + (k[p] + k[q]);

        // cout<<"! "<<y<<" "<<k[y]<<" "<<b[y]<<"|"<<o<<" "<<k[o]<<" "<<b[o]<<"|";

        // cout<<ans<<"\n";

        if (deg[y] == 1) {
            if (len - 1 < 32) {
                calc(y, -1);
                ans = min(ans, k[x] + b[x]);
            }
        } else if (deg[y] == 2) {
            if (len < 32) {
                calc(y, -1);
                ans = min(ans, k[y] + b[y]);
            }
        }

        dfs2(y, x, len);

        k[y] = old_k_y, b[y] = old_b_y;
        k[x] = old_k_x, b[x] = old_b_x;
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        e[i] = make_pair(x, y);
    }

    if (m >= n) {
        cout << "NIE\n";
        return;
    }
    for (int i = 1; i < n; i++) {
        int x = e[i].first;
        int y = e[i].second;
        son[x].push_back(y);
        son[y].push_back(x);
        deg[x]++;
        deg[y]++;
    }

    for (int i = 1; i <= n; i++) {
        if (deg[i] > 3) {
            cout << "NIE\n";
            return;
        }
    }

    dfs1(1, 0);

    if (dia / 2 >= 32) {
        cout << "NIE\n";
        return;
    }

    ans = inf;
    if (deg[1] == 1) {
        if (maxn[1] - 2 < 32)
            ans = min(ans, k[u[1]] + b[u[1]]);
    } else if (deg[1] == 2) {
        if (maxn[1] - 1 < 32)
            ans = min(ans, k[1] + b[1]);
    }

    dfs2(1, 0, 0);
    if (ans == inf) {
        cout << "NIE\n";
        return;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n = 1;
    // cin>>n;
    while (n--)
        solve();
    return 0;
}