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

int n, k;
int dp[200005];
vector <int> Adj[200005];

int ans;
int f[200005];
int r[200005];

void DFS(int node, int maxx, int p = 0)
{
	r[node] = 1;
	for(auto x : Adj[node])
	{
		if(x == p)
		{
			continue;
		}
		DFS(x, maxx, node);
		r[node] = max(r[node], r[x] + 1);
	}
	if(r[node] <= f[node])
	{
		r[node] = 0;
	}
	if(r[node] == maxx + 1)
	{
		r[node] = 0;
		f[node] = maxx + 1;
		ans++;
	}
	f[p] = max(f[p], f[node] - 1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// freopen("Input.txt", "r", stdin);
	// freopen("Output.txt", "w", stdout);
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
	{
		int u, v;
		cin >> u >> v;
		Adj[u].push_back(v);
		Adj[v].push_back(u);
	}
	int ll = 1, rr = 2e5;
	while(ll < rr)
	{
		ans = 0;
		int mid = (ll + rr) >> 1;
		for(int i = 1; i <= n; i++)
		{
			r[i] = 0;
			f[i] = 0;
		}
		DFS(1, mid);
		if(r[1])
		{
			ans++;
		}
		if(ans <= k)
		{
			rr = mid;
		}
		else
		{
			ll = mid + 1;
		}
	}
	cout << ll;
}
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<complex>
#include<cstdio>
#define initdp(a,b) for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)dp[i][j]=-1;
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ppi pair<pii,int>
#define pip pair<int,pii>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define inf 1000000001
#define inf1 1000000000000000001
#define mod 1000000007
#define pie 3.14159265358979323846
#define N 1000005
#define mid(l,r) l+(r-l)/2
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int ddx[8]={1,1,0,-1,-1,-1,0,1},ddy[8]={0,1,1,1,0,-1,-1,-1};
void mad(ll &a,ll b){a=(a+b)%mod;if(a<0)a+=mod;}
ll gcd(ll a,ll b){ if(!a)return b;return gcd(b%a,a);}
int ed[20][20];
int n,m;
//int dp[20][1<<20];
int dp[1<<20];
/*int pos[1<<20];
int rec(int u,int mask){
	if(mask+1==(1<<n)||u==n)return 0;
	if(dp[u][mask]!=m+1)return dp[u][mask];
	if(mask&(1<<u))return dp[u][mask]=rec(u+1,mask);
	int &res=dp[u][mask]=1+rec(u+1,mask|(1<<u));
	int newmask=(1<<u);
	for(int i=0;i<n;i++){
		//if(mask&(1<<i))continue;
		if(!ed[u][i])continue;
		newmask|=(1<<i);
	}
	for(int i=newmask;i;i=(i-1)&newmask)
	if(pos[i]){//cout<<i<<"\n";
		res=min(res,1+rec(u+1,mask|i));
		break;
	}
	return res;
}*/
void solve(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		u--;
		v--;
		ed[u][v]=ed[v][u]=1;
	}
	for(int i=0;i<n;i++)ed[i][i]=1;
	//for(int i=0;i<n;i++)
		for(int j=0;j<(1<<n);j++)dp[j]=inf;
	for(int i=0;i<(1<<n);i++){
		int f=0;
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				if(!(i&(1<<j)))continue;
				if(!(i&(1<<k)))continue;
				if(!ed[j][k]){f=1;break;}
			}
		}
		if(!f){
			//pos[i]=1;
			//if(i&1)dp[0][i]=1;
			dp[i]=1;
		}
		//cout<<i<<" "<<pos[i]<<"\n";
	}
	/*for(int i=1;i<n;i++){
		for(int mask=0;mask<(1<<n);mask++){
			if(!(mask&(1<<i)))continue;
			dp[i][mask]=min(dp[i][mask],dp[i-1][mask]);
			for(int s=mask;s;s=(s-1)&mask){
				if(pos[mask^s])dp[i][mask]=min(dp[i][mask],1+dp[i-1][s]);
			}
		}
	}*/

	for(int mask=1;mask<(1<<n);mask++){
		for(int s=mask;s;s=(s-1)&mask){
			dp[mask]=min(dp[mask],dp[mask^s]+dp[s]);
		}
		//cout<<dp[mask]<<"\n";
	}
	//cout<<pos[(1<<n)-1];
	//cout<<rec(0,0);
	//cout<<dp[n-1][(1<<n)-1];
	cout<<dp[(1<<n)-1];
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}
}