#include <iostream>

#include <algorithm>

#include <string.h>

#include <cstdio>

#include <queue>

#include <vector>

using namespace std;

const int maxn=;

typedef long long ll;

struct point{

   int L,R;

   int Rper;

   ll len;

   point(int a=,int c=, int d=,ll e=){

       L=a;  R=c; Rper=d;  len=e;

   }

};

vector<int> F[];

queue<point> Q;

int main()

{

    int cas=;

    scanf("%d",&cas);

    for(int cc=; cc<=cas; ++cc){

        int n,k;

        scanf("%d%d",&n,&k);

        for(int i=; i<=n; ++i) F[i].clear();

       while(!Q.empty())Q.pop();

        int rea=,frt=;

        point t1,t2;

        for(int i=; i<n; ++i){

            int a,b;

            scanf("%d%d",&a,&b);

            F[a].push_back(b);

            F[b].push_back(a);

            Q.push(point(a,b,a,));

            rea++;

            Q.push(point(b,a,b,));

            rea++;

        }

        ll ans=;

        for(frt=; frt<*k; ++frt){

                t1= Q.front();

                Q.pop();

             ans=ans+t1.len;

             if(rea>=*k) {continue;}

               int sz = F[t1.R].size();

        for(int i=; i<sz; ++i){

                 int  to = F[t1.R ][i];

                 if(to!=t1.Rper&&rea<*k){

                     t2.L=t1.L;

                     t2.len=t1.len+;

                     t2.R=to;

                     t2.Rper=t1.R;

                     rea++;

                     Q.push(t2);

                 }

             }

        }

        printf("%I64d\n",ans/);

    }

    return ;

}