#include <bits/stdc++.h>

using namespace std;
#define  ll long long
#define ld long double
#define f first
#define s second
const int N = 20;

int n , m , ans , cur , dp[1<<N];
bool edge[N][N] , good[1<<20];
vector<int> v;

void solve(int i)
{
    if (i == n)
    {
        for(int j=0; j<v.size(); j++)
        {
            for(int jj=j+1; jj<v.size(); jj++)
            {
                if (!edge[v[j]][v[jj]]) return;
            }
        }
        good[cur] = 1;
        return;
    }

    v.push_back(i);
    cur |= (1<<i);
    solve(i+1);
    v.pop_back();
    cur ^= (1<<i);
    solve(i+1);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin >> x >> y;
        x-- , y--;
        edge[x][y] = 1 , edge[y][x] = 1;
    }


    solve(0);

    ll tmp = 1<<n;

    for(int i=1; i<=tmp; i++)
    {
        dp[i] = 1e9;
    }

    for(int i=1; i<tmp; i++)
    {
        if (good[i]) dp[i] = min(dp[i] , 1);

        for(int j=i; j>0; j = ((j-1)&i) )
        {
            if (good[i^j])
                dp[i] = min(dp[i] , dp[j]+1);
        }
    }

    cout << dp[tmp-1] << '\n';

    return 0;
}
#include <cstdio>
#include <algorithm>
const int Maxn=200000;
const int Inf=0x3f3f3f3f;
int n,k;
int head[Maxn+5],arrive[Maxn<<1|5],nxt[Maxn<<1|5],tot;
void add_edge(int from,int to){
	arrive[++tot]=to;
	nxt[tot]=head[from];
	head[from]=tot;
}
int dis;
int num;
int f_1[Maxn+5],f_2[Maxn+5];
void work_dfs(int u,int fa){
	f_1[u]=-Inf;
	f_2[u]=Inf;
	for(int i=head[u];i;i=nxt[i]){
		int v=arrive[i];
		if(v==fa){
			continue;
		}
		work_dfs(v,u);
		f_1[u]=std::max(f_1[u],f_1[v]+1);
		f_2[u]=std::min(f_2[u],f_2[v]+1);
	}
	if(f_2[u]>dis){
		f_1[u]=std::max(f_1[u],0);
	}
	if(f_1[u]+f_2[u]<=dis){
		f_1[u]=-Inf;
	}
	if(f_1[u]>=dis){
		num++;
		f_2[u]=0;
		f_1[u]=-Inf;
	}
}
bool check(int x){
	dis=x;
	num=0;
	work_dfs(1,0);
	if(f_1[1]>=0){
		num++;
	}
	return num<=k;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v);
		add_edge(v,u);
	}
	int left=1,right=n;
	while(left<right){
		int mid=(left+right)>>1;
		if(check(mid)){
			right=mid;
		}
		else{
			left=mid+1;
		}
	}
	printf("%d\n",left);
	return 0;
}
