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

const int MAX = 2e5 + 5;

vector<int> grph[MAX];
int level[10000];
int visited[10000];
vector<int> distance_From_source(MAX);

int BFS(int source, int destination){
    visited[source] = 1;
    level[source] = 0;

    queue<int> q;
    q.push(source);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < grph[x].size(); i++){
            int y = grph[x][i];
            if(visited[y] == 0){
                visited[y] = 1;
                if(level[y] == 0){
                    level[y] = level[x] + 1;
                    q.push(y);
                }

            }
        }
    }
    distance_From_source[destination] = level[destination];

}

int solve(){
    int n, k , a, b, sm = 0;
    cin  >> n >> k;
    memset(grph, 0, sizeof(grph));
    for(int i = 0; i < n - 1; i++){
        cin >> a >> b;
        grph[a].push_back(b);
    }
    for(int i = 1; i <= n; i++){
        BFS(1, i);
    }
    sort(distance_From_source.begin(), distance_From_source.end());
    reverse(distance_From_source.end(), distance_From_source.end());
    for(int x = 0; x < k; x++){
        sm += distance_From_source[x];
    }
    cout << sm  << endl;
}


int main() {
int t; cin >> t;

while(t--) {
   solve();
}
}