#include<cstdio>
#define max(a,b) ((a)>(b)? (a):(b))
#define min(a,b) ((a)<(b)? (a):(b))
typedef long long ll;
const ll inf=1e8;
int n,m,res=0,cnt=0,tot=0;
int b[300005];
ll f[300005],g[300005];
int h[300005],to[600005],ver[600005];
inline int read() {
	register int x=0,f=1;register char s=getchar();
	while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
	while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
	return x*f;
}
inline void add(int x,int y) {
	to[++cnt]=y;
	ver[cnt]=h[x];
	h[x]=cnt;
}
void dfs(int x,int fa,int mid)
{
	f[x]=-inf;g[x]=inf;
	for(register int i=h[x];i;i=ver[i])
    {
		int y=to[i];
		if(y==fa) continue;
		dfs(y,x,mid);
		f[x]=max(f[x],f[y]+1);
		g[x]=min(g[x],g[y]+1);
	}
	if(f[x]+g[x]<=mid) f[x]=-inf;
	if(g[x]>mid&&b[x]==1) f[x]=max(f[x],0);
	if(f[x]==mid) f[x]=-inf,g[x]=0,++tot;
}
int check(int x) {
	tot=0;
	dfs(1,-1,x);
	if(f[1]>=0) ++tot;
	return tot<=m;
}
int main() {
	n=read(),m=read();
	for(register int i=1;i<=n;++i) b[i]=1;
	for(register int i=1;i<n;++i) {
		int x=read(),y=read();
		add(x,y);add(y,x);
	}
	int L=0,R=n;
	while(L<=R) {
		int mid=L+R>>1;
		if(check(mid)) {R=mid-1;res=mid;}
		else {L=mid+1;}
	}
	printf("%d\n",res);
	return 0;
}
 
#include <bits/stdc++.h>

#define Fast cin.tie(0), ios::sync_with_stdio(0)
#define All(x) x.begin(), x.end()
#define louisfghbvc int t; cin >> t; for(int tt = 0; tt < t; ++tt)
#define sz(x) (int)(x).size()
#define sort_unique(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()));
using namespace std;
typedef long long LL;
typedef pair<LL, LL> ii;
typedef vector<LL> vi;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T> istream& operator>>(istream &is, vector<T> &v) { for(auto &it : v) is >> it; return is; }
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep = ""; for(const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cerr << " end.\n"; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

const int N = 800 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
/**
Read problem statement carefully
**/
int arr[N][N];

int n, k;
bool check(int mid, int L){
    vector<vector<int>> pre(n+1, vector<int>(n+1));
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + (arr[i-1][j-1] >= mid);

    bool ok = 1;
    for(int i = 0; i+k <= n; ++i){
        for(int j = 0; j+k <= n; ++j){
            int res = pre[i+k][j+k] - pre[i+k][j] - pre[i][j+k] + pre[i][j];
            if(res < L) ok = 0;
        }
    }
    return ok;
}

void solve(int T){
    int n, m;
    cin >> n >> m;
    map<int, vector<int>> mp;
    for(int i = 0, x, y; i < m; ++i){
        cin >> x >> y;
        mp[x].push_back(y);
    }
    
    set<int> st;
    st.insert(n);
    for(auto &[x, v]: mp){
        vector<int> add;
        for(auto &y: v){
            if(st.count(y-1) || st.count(y+1))
                add.push_back(y);
        }
        for(auto &y: v) st.erase(y);
        for(auto &y: add) st.insert(y);
    }

    cout << sz(st) << "\n";
}

int main()
{
    Fast;
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // louisfghbvc
        solve(1);
    return 0;
}

/**
Enjoy the problem.
**/
