#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(a.k, b.k));
}

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] - 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]] - depth[id]) + 1);
        initRootDepth(sons[id][1], max(up, tree_depth[sons[id][0]] - depth[id]) + 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;
        }
    }
    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] + root_depth[id] > 33) {
            return;
        }
        if (id == rt) {
            if (l[id] == 0) {
                ans = min(ans, 0);
            } else if (l[id] == 1) {
                ans = min(ans, getValue(tree_func[sons[id][0]], 1));
            } else if (id == rt && 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;
}

answer.code: In function ‘void calculatetMin(int, Func)’:
answer.code:143:26: error: no matching function for call to ‘min(long long int&, int)’
  143 |                 ans = min(ans, 0);
      |                       ~~~^~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from answer.code:2:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)’
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
answer.code:143:26: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
  143 |                 ans = min(ans, 0);
      |                       ~~~^~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)’
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   template argument deduction/substitution failed:
answer.code:143:26: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
  143 |                 ans = min(ans, 0);
      |                       ~~~^~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)’
 5775 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note:   template argument deduction/substitution failed:
answer.code:143:26: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
  143 |                 ans = min(ans, 0);
      |                       ~~~^~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)’
 5785 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note:   template argument deduction/substitution failed:
answer.code:143:26: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
  143 |                 ans = min(ans, 0);
      |                       ~~~^~~~~~~~
answer.code: In function ‘void init()’:
answer.code:42:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   42 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
answer.code:47:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   47 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~