#include <bits/stdc++.h>
#define int long long int
#include <time.h>
using namespace std;
int graph[22][22];
int g[22];
int ind_set[2000006];
int co[2000006];
bool vis[22];
bool good = true; ;
int n;
int coll[22];
void dfs(int no , int s , int p , int colou ){
    vis[no] = 1;
    coll[no] = colou;
    for(int j = 0;j<n;j++){
        if(j == p ){continue;}
        if(graph[no][j] ){
            if(s&(1<<j) ){
                if(vis[j] ){
                    if(coll[j]^colou ){
                        ;
                    }
                    else{
                        good = false;return ;
                    }
                }
                else{
                    dfs(j , s , no , colou^1 );
                }
            }
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int  m;
    cin>>n>>m;
    for(int i = 1;i<= m;i++){
        int l , r;
        cin>>l>>r;
        l--;
        r--;
        graph[l][r] = 1;
        graph[r][l] = 1;
        g[l]+= (1<<r);
        g[r]+= (1<<l );
    }
    ind_set[0] = 1;
    for(int i = 0;i<n;i++){
        ind_set[1<<i ] = 1;
    }
    for(int i = 1;i<(1<<n ) ;i++){
        if(ind_set[i] ){
            for(int j = 0;j<n;j++ ){
                if(i&(1<<j ) ){
                    ;
                }
                else{
                    if(i&g[j] ){
                        ;
                    }
                    else{
                        ind_set[i|(1<<j)] = 1;
                    }
                }
            }
        }
    }
    for(int i = 1;i<(1<<n);i++){
        good = true;
        for(int j = 0;j<n;j++){
            vis[j] = 0;
            coll[j] = 0;
        }
        int ce = 0;
        for(int j = 0;j<n;j++){
            if(i&(1<<j) ){
                if(!vis[j] ){
                    dfs(j , i , -1 , 0 );
                    ce++;
                    if(!good){break;}
                }
            }
        }
        if(good ){
            co[i] = ce;
        }
        else{
            co[i] = 0;
        }
    }
    int ans = 0;
    int ma = (1<<n)-1;
    for (int m=0; m<(1<<n); ++m){
        int z = m^ma;
        if(m == 0){
            if(ind_set[z]){
                ans++;
            }
            continue;
        }
        if(ind_set[z] ){
            if(co[m] ){
                ans+= (1<<co[m] );
            }
        }
    }
    cout<<ans;
}

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

const int maxn = 200010;
int n, K, lst[maxn], tmp[maxn];
vector<int> G[maxn];

int main() {
    scanf("%d %d", &n, &K);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    auto chk = [&](int x) {
        memset(lst, 0x3f, sizeof(lst));
        int cnt = 0;
        function<void(int, int)> dfs = [&](int v, int fa) {
            for (int u : G[v]) if (u ^ fa) {
                dfs(u, v);
                lst[v] = min(lst[v], lst[u] + 1);
            }
            int mx = -n;
            if (lst[v] > x) mx = 1;
            for (int u : G[v]) if (u ^ fa && lst[v] + tmp[u] > x) {
                mx = max(mx, tmp[u] + 1);
            }
            if (mx > x) cnt++, tmp[v] = -n, lst[v] = 0;
            else tmp[v] = mx;
        };
        dfs(1, 0);
        if (tmp[1] > 0) cnt++;
        return cnt;
    };
    int l = 1, r = n, ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        chk(mid) <= K ? r = (ans = mid) - 1 : l = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}