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

const int INF = 1e9;

vector<int> adj[200005];
int n, k;
array<int, 3> dp[200005]; // (#special, min dist(u, special), max dist(u, not satisfy yet))

array<int, 3> combine(array<int, 3> a, array<int, 3> b, int d) {
    array<int, 3> res;
    res[0] = a[0] + b[0];
    res[1] = min(a[1], b[1] + 1);
    res[2] = max(a[2], b[2] + 1);

    if (res[1] + res[2] <= d) {
        res[2] = -INF;
    }
    else if (res[2] == d) {
        res[0]++;
        res[1] = 0;
        res[2] = -INF;
    }
    return res;
}

void dfs(int u, int p, int d) {
    dp[u] = {0, d + 1, 0};

    for (auto i: adj[u]) {
        if (i == p) continue;
        dfs(i, u, d);
        dp[u] = combine(dp[u], dp[i], d);
    }
    // cout << u << " " << dp[u][0] << " " << dp[u][1] << " " << dp[u][2] << endl; 
}

int solve(int d) {
    dfs(1, 0, d);
    return dp[1][0] + (dp[1][2] >= 0);
    // cout << dp[1][0] << endl;
}

int main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    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);
    }
    // cout << solve(2) << endl;
    // return 0;
    // for (int i = 1; i <= n; i++) {
    //     cout << solve(i) << " ";
    // }
    // return 0;
    int lower = 1, upper = n;
    while (lower < upper) {
        int mid = (lower + upper) / 2;
        if (solve(mid) <= k) {
            upper = mid;
        } 
        else lower = mid + 1;
    }

    cout << lower << endl;

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

int main() {
	long long N, M; cin >> N >> M;
	vector<long long> X(M), Y(M);
	for (int i = 0; i < M; i++) cin >> X[i] >> Y[i];

	set<pair<long long, long long>> Set;
	for (int i = 0; i < M; i++) {
		Set.insert(make_pair(X[i], Y[i]));
	}

	set<long long> Sec;
	Sec.insert(N);
	Sec.insert(-(1LL << 60)); Sec.insert(1LL << 60); Sec.insert(1LL << 59);
	long long prev = 0;
	set<long long> help, help2;
	for (int i = 0; i < M; i++) {
		auto a = *Set.begin();
		Set.erase(Set.begin());
		if (prev != a.first) {
			while (!help2.empty()) {
				Sec.erase(*help2.begin());
				help2.erase(help2.begin());
			}
			while (!help.empty()) {
				Sec.insert(*help.begin());
				help.erase(help.begin());
			}
          	prev = a.first;
		}
		auto b = Sec.lower_bound(a.second);
		if (*b == a.second) help2.insert(a.second); b--;
		if (*b == a.second - 1) help.insert(a.second); b++;
		if (*b == a.second + 1) help.insert(a.second); b++;
		if (*b == a.second + 1) help.insert(a.second);
	}

	while (!help2.empty()) {
		Sec.erase(*help2.begin());
		help2.erase(help2.begin());
	}
	while (!help.empty()) {
		Sec.insert(*help.begin());
		help.erase(help.begin());
	}

	cout << Sec.size() - 3 << endl;
}