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

const int MAXN = 1e5 + 10;
vector <int> edges[MAXN];
int parent[MAXN], n, k;

void dfs(int u, int v) {
    parent[v] = u;

    for (int x : edges[v]) {
        if (x != u) dfs(v, x);
    }
}

int dp[MAXN];
bool v[MAXN];

int f(int u) {
    if (v[u]) return dp[u];
    v[u] = 1;

    vector <int> ans;

    for (int x : edges[u]) {
        if (x == parent[u]) continue;
        ans.push_back(f(x));
    }

    sort(ans.begin(), ans.end(), greater <int> ());

    for (int i = 0; i < ans.size(); i++) {
        dp[u] = max(dp[u], 1 + i / k + ans[i]);
    }

    return dp[u];
}

vector <pair <int, int>> vec[MAXN];
vector <int> prefix[MAXN], suffix[MAXN];

void init(int u) {
    for (int x : edges[u]) {
        if (x == parent[u]) continue;
        vec[u].push_back({f(x), x});
    }

    sort(vec[u].begin(), vec[u].end(), greater <pair <int, int>> ());
    prefix[u].resize(vec[u].size());
    suffix[u].resize(vec[u].size());

    for (int i = 0; i < vec[u].size(); i++) {
        prefix[u][i] = max(i == 0 ? 0 : prefix[u][i - 1], 1 + i / k + vec[u][i].first);
    }

    for (int i = vec[u].size() - 1; i >= 1; i--) {
        suffix[u][i] = max(i + 1 == vec[u].size() ? 0 : suffix[u][i + 1], 1 + (i - 1) / k + vec[u][i].first);
    }

    for (int i = 0; i < vec[u].size(); i++) {
        int x = vec[u][i].second;
        if (x == parent[u]) continue;

        vec[x].push_back({(i == 0 ? 0 : prefix[u][i - 1]) + (i + 1 == suffix[u].size() ? 0 : suffix[u][i + 1]), u});
    }
}

void solve(int u, int v) {
    init(v);

    for (int x : edges[v]) {
        if (x != u) solve(v, x);
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    dfs(1, 1);
    solve(1, 1);

    int ans = INT_MAX;

    for (int u = 1; u <= n; u++) {
        ans = min(ans, prefix[u].empty() ? 0 : prefix[u].back());
    }

    cout << ans << '\n';
    return 0;

}