#include <bits/stdc++.h>
using namespace std;
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
#define Bit(mask , i) ((mask >> i) & 1)
#define fi first
#define se second
#define _LOG2(nl) 31 - __builtin_clz(nl)
#define c_bit(nl) __builtin_popcount(nl)
#define ii pair<long long , int>
#define lll pair<long long , pair<long long , long long>>
#define lii pair<long long , pair<long long , int>>
#define iii pair<int , pair<int , int>>
#define iiii pair<pair<int , int> , pair<int , int>>
#define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
#define li pair<long long , int>
#define db long double
#define onBit(mask , i) (mask | (1 << i))
#define offBit(mask , i) (mask & (~(1 << i)))

const long long INF = 1e16;
const int N = 3e5 + 7;
int n , m;
vector<int> a[N] , adj[N];
int col[N] , cnt[N] , topo[N] , p = 0 , c[N] , par[N];

struct gv{
    int val , id;
};

gv b[N];

bool cmp(gv x , gv y){
    return x.val > y.val;
}

void inp(){
    cin >> n >> m;
    for (int i = 1 ; i <= n + 1 ; ++i){
        par[i] = i;
    }
    for (int i = 1 ; i < n ; ++i){
        int u , v;
        cin >> u >> v;
        a[u].push_back(v);
        adj[v].push_back(u);
        ++c[v];
    }
}

int find_par(int u){
    if (u == par[u]) return u;
    return par[u] = find_par(par[u]);
}

void bfs(){
    queue<int> q;
    for (int i = 1 ; i <= n ; ++i) if (c[i] == 0){
        q.push(i);
        ++p;
        topo[p] = i;
    }

    while (q.size()){
        int u = q.front();
        q.pop();

        for (int v : a[u]){
            --c[v];
            if (c[v] == 0){
                q.push(v);
                ++p;
                topo[p] = v;
            }
        }
    }
}

void solve(){
    bfs();
    for (int i = p ; i >= 1 ; --i){
        int u = topo[i];

        int depth = 1;
        for (int v : a[u]) depth = max(depth , b[v].val + 1);
        b[u].val = depth;
        b[u].id = u;
    }
    sort(b + 1 , b + n + 1 , cmp);
    int res = 0;
    for (int i = 1 ; i <= p ; ++i){
        int u = b[i].id;
        int _max = 0;
        for (int v : adj[u]) _max = max(_max , col[v]);
        int need = _max + 1;
        int color = find_par(need);

        col[u] = color;
        res = max(res , color);
        cnt[color]++;

        if (cnt[color] == m)
        par[color] = find_par(color + 1);
    }
    cout << res;
}

int main(){
    faster;
    inp();
    solve();
    return 0;
}