1. #include <iostream>
2. #include <vector>
3.  
4. using namespace std;
5. int t,n,k,a,b;
6. vector<vector<int>>g;
7. vector<int>dp;
8. int rez=0,sol,cnt;
9. bool vizitat[100005];
10. void dfs_dinamica(int m, int nod)
11. {
12.     dp[nod]=1;
13.     vizitat[nod]=1;
14.     for(auto vecin:g[nod])
15.     {
16.         if(vizitat[nod]==0)
17.         {
18.             dfs_dinamica(m,vecin);
19.             dp[nod]+=dp[vecin];
20.         }
21.     }
22.     if(dp[nod]>=m)
23.     {
24.         dp[nod]=0;
25.         rez++;
26.     }
27. }
28. void caut_bin()
29. {
30.     int st=1,dr=n,m;
31.     rez=0;
32.     sol=0;
33.     while(st<=dr)
34.     {
35.         m=(st+dr)/2;
36.         cnt=0;
37.         for(int i=1; i<=n; i++)
38.         {
39.             vizitat[i]=0;
40.         }
41.         dfs_dinamica(m,1);
42.         if(rez>=k)
43.         {c
44.             st=m+1;
45.             sol=m;
46.         }
47.         else
48.         {
49.             dr=m-1;
50.         }
51.     }
52. }
53. int main()
54. {
55.     cin>>t;
56.     for(int j=1; j<=t; j++)
57.     {
58.         cin>>n>>k;
59.         g.resize(n+1);
60.         dp.resize(n+1);
61.         g=vector<vector<int>> {n+1};
62.         dp=vector<int> {n+1};
63.         for(int i=1; i<=n-1; i++)
64.         {
65.             cin>>a>>b;
66.             g[a].push_back(b);
67.             g[b].push_back(a);
68.         }
69.         caut_bin();
70.         cout<<sol<<"\n";
71.     }
72. }
73.