#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<array>
#include<algorithm>
using namespace std;
using LL = long long;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;
    if (m != n - 1){
        cout << "NIE" << '\n';
        return 0;
    }
    vector<vector<int> > g(n + 1);
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for(int i = 1; i <= n; i++){
        if (g[i].size() > 3){
            cout << "NIE" << '\n';
            return 0;
        }
    }

    auto bfs = [&](int st){
        queue<int> q;
        vector<int> d(n + 1, -1);
        d[st] = 0;
        q.push(st);
        while(!q.empty()){
            int t = q.front();
            q.pop();
            for(auto j : g[t]){
                if (d[j] == -1){
                    d[j] = d[t] + 1;
                    q.push(j);
                }
            }
        }
        return d;
    };

    auto d1 = bfs(1);
    int p = max_element(d1.begin(), d1.end()) - d1.begin();
    auto d2 = bfs(p);
    int q = max_element(d2.begin(), d2.end()) - d2.begin();
    auto d3 = bfs(q);

    int root = -1;
    for(int i = 1; i <= n; i++){
        if (max(d2[i], d3[i]) <= 31){
            root = i;
            break;
        }
    }

    if (root == -1){
        cout << "NIE" << '\n';
        return 0;
    }

    const LL INF = 1e18;
    LL ans = INF;

    vector<array<int, 32> > dp(n + 1), ndp(n + 1);
    vector<LL> f(n + 1, INF), nf(n + 1, INF);

    auto dfs1 = [&](auto &&dfs1, int u, int fa) -> void {
        dp[u][0] = 1;
        vector<int> sons;
        for(auto j : g[u]){
            if (j == fa) continue;
            dfs1(dfs1, j, u);
            sons.push_back(j);
            for(int i = 0; i + 1 <= 31; i++){
                dp[u][i + 1] += dp[j][i];
            }
        }
        if (sons.size() <= 2){
            if (sons.size() == 0){
                f[u] = 1;
            }
            else if (sons.size() == 1){
                f[u] = 1 + f[sons[0]];
                for(int i = 0; i + 1 <= 31; i++){
                    f[u] += (1LL << i) * dp[sons[0]][i];
                }
            }
            else{
                LL mn = 1e18;
                for(auto _ : {0, 1}){
                    swap(sons[0], sons[1]);
                    LL sum = 1 + f[sons[0]] + f[sons[1]];
                    for(int i = 0; i < 2; i++){
                        int j = sons[i];
                        for(int k = 0; k + 1 <= 31; k++){
                            f[u] += (1 + i) * (1LL << k) * dp[j][k];
                        }
                    }
                    mn = min(mn, sum);
                }
                f[u] = mn;
            }
        }
        f[u] = min(f[u], INF);
    };

    dfs1(dfs1, root, -1);

    auto dfs2 = [&](auto &&dfs2, int u, int fa, array<int, 32> pre, LL val) -> void {
        
        {
            int leaf = -1;
            vector<int> sons;
            for(auto j : g[u]){
                if (j == fa){
                    ndp[j] = pre;
                    nf[j] = val;
                }
                else{
                    ndp[j] = dp[j];
                    nf[j] = f[j];
                }
                if (g[j].size() == 1 and leaf == -1){
                    leaf = j;
                }
                else{
                    sons.push_back(j);
                }
            }
            
            if (sons.size() <= 2){
                LL mn = 1e18;
                if (sons.size() == 0){
                    mn = 1;
                }
                else if (sons.size() == 1){
                    mn = 1 + nf[sons[0]];
                    for(int i = 0; i + 1 <= 31; i++){
                        mn += (1LL << i) * ndp[sons[0]][i];
                    }
                }
                else{
                    for(auto _ : {0, 1}){
                        swap(sons[0], sons[1]);
                        LL sum = 1 + nf[sons[0]] + nf[sons[1]];
                        for(int i = 0; i < 2; i++){
                            int j = sons[i];
                            for(int k = 0; k + 1 <= 31; k++){
                                sum += (1 + i) * (1LL << k) * ndp[j][k];
                            }
                        }
                        mn = min(mn, sum);
                    }
                }
                ans = min(ans, mn);
            }
        }        
        for(auto j : g[u]){
            if (j == fa) continue;
            if (max(d2[j], d3[j]) > 31) continue;
            array<int, 32> cnt{};
            cnt[0] = 1;
            for(int i = 0; i + 1 <= 31; i++){
                cnt[i + 1] += pre[i];
            }
            vector<int> sons;
            for(auto k : g[u]){
                if (k != j){
                    sons.push_back(k);
                    for(int i = 0; i + 1 <= 31; i++){
                        cnt[i + 1] += ndp[k][i];
                    }
                }
            }
            LL mn = 1e18;
            if (sons.size() <= 2){
                if (sons.size() == 0){
                    mn = 1;
                }
                else if (sons.size() == 1){
                    mn = 1 + nf[sons[0]];
                    for(int i = 0; i + 1 <= 31; i++){
                        mn += (1LL << i) * ndp[sons[0]][i];
                    }
                }
                else{
                    for(auto _ : {0, 1}){
                        swap(sons[0], sons[1]);
                        LL sum = 1 + nf[sons[0]] + nf[sons[1]];
                        for(int i = 0; i < 2; i++){
                            int j = sons[i];
                            for(int k = 0; k + 1 <= 31; k++){
                                sum += (1 + i) * (1LL << k) * ndp[j][k];
                            }
                        }
                        mn = min(mn, sum);
                    }
                }
            }
            mn = min(mn, INF);
            dfs2(dfs2, j, u, cnt, mn);
        }

    };

    dfs2(dfs2, root, -1, {}, 0);

    if (ans == INF) cout << "NIE" << '\n';
    else cout << ans << '\n';


}