https://codeforces.com/contest/1946/problem/C

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef vector<long long> VI;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb(i) push_back(i)
#define int long long
#define INF 0x3f3f3f3f
#define oz  998244353
#define endl '\n'
#define N 100010
const int mod = 1e9 + 7;


int p[N], si[N];
int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}
//size[find(b)] += size[find(a)];
//p[find(a)] = find(b);


int n, m;
VI g[N];
int cnt;

int dfs(int now, int la, int x) { //遍历树判断能连通块大小为x能分成几份，由叶子节点向上判断

    int num = 1;

    for (auto to : g[now]) {
//      int num = 1;
        if (to == la)continue;
        num += dfs(to, now, x); // 加上左子树点数和右子树点数
    }

    if (num >= x) {
        cnt ++;
        return 0; //子树满足节点则剪枝 cnt++
    }

    return num;
}

int check(int x) {
    cnt = 0;
    dfs(1, -1, x);
    return cnt > m;
}

void solve() {
    cin >> n >> m;

    rep(i, 1, n)g[i].clear();

    rep(i, 1, n - 1) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    int l = 0, r = n + 1;

    while (l + 1 < r) { //二分答案找最值
        int mid = l + r >> 1;

        if (check(mid))l = mid;
        else r = mid;

    }

    if(check(l))cout << l << endl;
    else cout << r << endl;
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T --)

        solve();

    return 0;
}