///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 2e5 + 10;
const ll INF = 1e18;
const ll LOG = 20;
ll n, k;
ll h[MXN], dis[MXN], Jad[LOG][MXN];
vector<ll> adj[MXN], Ver;
void DFS(ll u, ll par, ll d, ll m){
    if(d > m || d >= dis[u]) return;
    dis[u] = d;
    for(auto v : adj[u]){
        if(v != par) DFS(v, u, d + 1, m);
    }
}
void dfs(ll u, ll par){
    Jad[0][u] = par;
    for(int i = 1; i < LOG; i ++){
        Jad[i][u] = Jad[i - 1][Jad[i - 1][u]];
    }
    Ver.push_back(u);
    for(auto v : adj[u]){
        if(v != par) h[v] = h[u] + 1, dfs(v, u);
    }
}
ll K_Jad(ll u, ll k){
    for(int i = 0; i < LOG; i ++){
        if((k >> i) & 1LL) u = Jad[i][u];
    }
    return u;
}
ll check(ll x){
    ll ans = 0;
    for(int i = 1; i <= n; i ++) dis[i] = INF;
    for(auto u : Ver){
        if(dis[u] <= x) continue;
        ans ++;
        DFS(K_Jad(u, min(h[u], x)), 0, 0, x);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i < n; i ++){
        ll u, v; cin >> u >> v;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    dfs(1, 0);
    sort(Ver.begin(), Ver.end(), [&](const int& u, const int &v){
        return h[u] > h[v];
    });
    ll l = 0, r = n;
    while(r - l > 1){
        ll mid = (l + r) / 2;
        if(check(mid) <= k) r = mid;
        else                l = mid;
    }
    cout << r << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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

// #include <atcoder/all>
// using namespace atcoder;
// using mint = modint1000000007;
// // using mint = modint998244353;

typedef int64_t Int;
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

template<class T> 
istream &operator>>(istream &is, vector<T> &v) { 
    for (auto &e : v) {
        is >> e; 
    }
    return is; 
}

bool print_space_enable = false;
void print() { 
    std::cout << '\n'; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) std::cout << " ";
    std::cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << '\n';
}

template<class T>
vector<T> make_vec(size_t n, T val) {
    return vector<T>(n, val);
}

template<class... Ts>
auto make_vec(size_t n, Ts... ts) {
    return vector<decltype(make_vec(ts...))>(n, make_vec(ts...));
}

void fast_IO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

Int rec(vector<Int> &dp, Int state) {
    if (dp[state] != INF) return dp[state];
    for (Int bit = state & (state - 1); bit > 0; bit = (state & (bit - 1))) {
        dp[state] = min(dp[state], rec(dp, bit) + rec(dp, state - bit));
    }
    return dp[state];
}

void solve() {
    fast_IO();
    Int n, m;
    cin >> n >> m;
    vector<Int> a(m), b(m);
    auto c = make_vec(n, n, false);
    for (Int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
        a[i]--, b[i]--;
        c[a[i]][b[i]] = c[b[i]][a[i]] = true;
    }
    auto dp = make_vec(1<<n, INF);
    dp[0] = 0;
    vector<bool> d(1<<n, true);
    for (Int bit = 1; bit < (1<<n); bit++) {
        for (Int i = 0; i < n - 1; i++) {
            for (Int j = i + 1; j < n; j++) {
                if ((bit & (1<<i)) and (bit & (1<<j)) and (not c[i][j])) {
                    d[bit] = false;
                }
            }
        }
        if (d[bit]) {
            dp[bit] = 1;
        }
    }
    print(rec(dp, (1<<n) -1));
}

int main() {
    solve();
    //Int _t; cin >> _t; while (_t--) solve();
    return 0;
}
