#include <cstdio>
#include <algorithm>
using namespace std;

struct Func {
    long long k, b;
};

int n, m, head[200000], to[400000], nxt[400000], out[400000], vst[400000], u, v;
int rt, flag, root_depth[200000], depth[200000], tree_depth[200000], sons[200000][2], l[200000];
Func tree_func[200000];
long long ans = 1e18;

Func make(long long k, long long b) {
    Func nw;
    nw.k = k;
    nw.b = b;
    return nw;
}

long long getValue(Func f, long long x) {
    return f.k * x + f.b;
}

Func grower(Func a) {
    return make((a.k << 1) + 1, a.b);
}

Func combine(Func a, Func b) {
    return make((a.k + b.k << 1) + 1, a.b + b.b + min(getValue(a, 1), getValue(b, 1)));
}

void add(int id, int u, int v) {
    to[id] = v;
    nxt[id] = head[u];
    head[u] = id;
    out[u] ++;
    return;
}

void init() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i ++) {
        head[i] = -1;
    }
    for (int i = 0; i < m; i ++) {
        scanf("%d %d", &u, &v);
        add(i << 1, u - 1, v - 1);
        add(i << 1 | 1, v - 1, u - 1);
    }
    return;
}

void buildTree(int id, int fa) {
    l[id] = 0;
    for (int i = head[id]; i >= 0; i = nxt[i]) {
        if (to[i] ^ fa) {
            sons[id][l[id] ++] = to[i];
            buildTree(to[i], id);
        }
    }
    return;
}

void initDepth(int id) {
    tree_depth[id] = depth[id];
    for (int i = 0; i < l[id]; i ++) {
        depth[sons[id][i]] = depth[id] + 1;
        initDepth(sons[id][i]);
        tree_depth[id] = max(tree_depth[sons[id][i]], tree_depth[id]);
    }
    return;
}

void initRootDepth(int id, int up) {
    root_depth[id] = max(tree_depth[id], up);
    if (l[id] == 1) {
        initRootDepth(sons[id][0], up + 1);
    } else if (l[id] == 2) {
        initRootDepth(sons[id][0], max(up, tree_depth[sons[id][1]]) + 1);
        initRootDepth(sons[id][1], max(up, tree_depth[sons[id][0]]) + 1);
    }
    return;
}

void initFunc(int id) {
    Func f[2];
    for (int i = 0; i < l[id]; i ++) {
        initFunc(sons[id][i]);
        f[i] = tree_func[sons[id][i]];
    }
    if (l[id] == 0) {
        tree_func[id] = make(1, 0);
    } else if (l[id] == 1) {
        tree_func[id] = grower(f[0]);
    } else if (l[id] == 2) {
        tree_func[id] = combine(f[0], f[1]);
    }
    return;
}

void build() {
    if (m ^ n - 1) {
        flag = 1;
        return;
    }
    for (int i = 0; i < n; i ++) {
        if (out[i] > 3) {
            flag = 1;
            return;
        }
    }
    for (rt = 0; rt < n; rt ++) {
        if (out[rt] ^ 3) {
            break;
        }
    }
    if (n > 1e4) {
        return;
    }
    buildTree(rt, rt);
    initDepth(rt);
    initRootDepth(rt, 0);
    for (rt = 0; rt < n; rt ++) {
        if (out[rt] + root_depth[rt] <= 33 && (out[rt] ^ 3)) {
            break;
        }
    }
    if (rt == n) {
        flag = 1;
        return;
    }
    buildTree(rt, rt);
    initDepth(rt);
    initFunc(rt);
    return;
}

void calculatetMin(int id, Func f) {
    if (out[id] ^ 3) {
        if (out[id] + tree_depth[id] > 33) {
            return;
        }
        if (id == rt) {
            if (l[id] == 1) {
                ans = min(ans, getValue(tree_func[sons[id][0]], 1));
            } else if (l[id] == 2) {
                ans = min(ans, getValue(tree_func[id], 1));
            }
        } else {
            if (l[id] == 0) {
                ans = min(ans, getValue(f, 1));
            } else if (l[id] == 1) {
                ans = min(ans, getValue(combine(tree_func[sons[id][0]], f), 1));
            }
        }
    }
    if (l[id] == 1) {
        calculatetMin(sons[id][0], grower(f));
    } else if (l[id] == 2) {
        calculatetMin(sons[id][0], combine(tree_func[sons[id][1]], f));
        calculatetMin(sons[id][1], combine(tree_func[sons[id][0]], f));
    }
    return;
}

void calculate() {
    if (flag) {
        printf("NIE\n");
    } else {
        calculatetMin(rt, make(0, 0));
        printf("%lld\n", ans);
    }
    return;
}

void solve() {
    init();
    build();
    calculate();
    return;
}

int main() {
    solve();
    return 0;
}