import sys
input = sys.stdin.read
from collections import defaultdict, deque
def max_nodes_visited(N, K, edges):
# Building the tree
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# Step 1: Calculate subtree sizes and depths using DFS
subtree_size = [0] * (N + 1)
depth = [0] * (N + 1)
visited = [False] * (N + 1)
def dfs(node, d):
visited[node] = True
depth[node] = d
subtree_size[node] = 1
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(neighbor, d + 1)
subtree_size[node] += subtree_size[neighbor]
dfs(1, 0)
# Step 2: Calculate potential revisits sorted by subtree size
nodes_by_subtree = sorted(range(1, N + 1), key=lambda x: -subtree_size[x])
# Step 3: Simulate revisiting up to K nodes to maximize coverage
total_visited = 0
revisited = 0
visited_nodes = set()
for node in nodes_by_subtree:
if revisited < K:
total_visited += subtree_size[node]
revisited += 1
else:
break
# Ensure the total nodes counted doesn't exceed N
total_visited = min(total_visited, N)
return total_visited
# Example usage:
data = input().split()
index = 0
T = int(data[index])
index += 1
results = []
for _ in range(T):
N, K = int(data[index]), int(data[index + 1])
index += 2
edges = []
for __ in range(N - 1):
u, v = int(data[index]), int(data[index + 1])
edges.append((u, v))
index += 2
results.append(str(max_nodes_visited(N, K, edges)))
# Output all results
print("\n".join(results))