Read problem statements in [Vietnamese],
[Bengali], [Mandarin Chinese], and [Russian] as well. 

You are given a tree with $n$ vertices (numbered $1, 2, \dots, n$) and an integer $k$.

A subtree is defined as a connected subgraph of the tree. That is, a subtree is another tree that can be obtained by removing some (possibly none) vertices and all edges incident to those vertices from $T$.

A subset $S$ of vertices is called good if every subtree containing all the nodes in $S$ has at least $k$ nodes. 

Find the size of the smallest good subset.

------  Input ------

The first line contains a single integer $T$, the number of test cases. The descriptions of test cases follow.
The first line of each testcase contains two integers, $n$ and $k$.
The next $n-1$ lines each contains two integers $u$, $v$, denoting an edge between vertices $u$ and $v$ of the tree.

------  Output ------

For each test case print in a single line, the minimum size of a good subset.

------  Constraints ------

$1≤ n≤ 10^{5}$
$1 ≤ k ≤ n$
$1 ≤ u, v ≤ n$
The given edges for each test case form a tree.
The sum of $n$ over all test cases is at most $10^{6}$.

------ Subtasks ------
Subtask #1 (30 points): $1 ≤ n ≤ 10^{3}$

Subtask #2 (70 points): original constraints

------  Sample Input ------

2
7 5
1 2
2 3
3 4
3 5
5 6
3 7
6 4
1 2
1 3
1 4
1 5
1 6

------  Sample Output ------

2
3

------  Explanation ------

Test Case $1$:
Consider the set $S = \{1, 6\}$.

The smallest subtree that contains both of the vertices in $S$ is the path between them ($1 \to 2 \to 3 \to 5 \to 6$) which contains $5$ vertices. Hence for $k = 5$, the answer is $2$.

Test Case $2$:
Consider the set $S = \{2, 3, 4\}$.

The smallest subtree that contains these three vertices includes $4$ nodes $\{1, 2, 3, 4\}$.

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Range queries

Segment trees revisited

Greedy algorithms

Data structures

Tree queries


Solutions:
__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from sys import stdin, stdout
WHITE = 0
GRAY = 1
BLACK = 2
read_numbers = lambda : list(map(int, stdin.readline().strip().split()))
output_line = lambda x: stdout.write(x)

def find_farthest_leaf(N, E, root=0):
	color = [WHITE] * N
	farthest_leaf = root
	level = 0
	max_level = 0
	color[root] = GRAY
	stack = [root]
	while stack:
		cur = stack[-1]
		if color[cur] == BLACK:
			stack.pop()
			level -= 1
			continue
		level += 1
		if level >= max_level:
			max_level = level
			farthest_leaf = cur
		for child in E[cur]:
			if color[child] == BLACK:
				continue
			if color[child] == WHITE:
				color[child] = GRAY
				stack.append(child)
		color[cur] = BLACK
	return farthest_leaf

def search_strips(N, E, root):
	color = [WHITE] * N
	strips = [[] for _ in range(N)]
	children = [[] for _ in range(N)]
	leafs = [False] * N
	color[root] = GRAY
	stack = [root]
	while stack:
		cur = stack[-1]
		if color[cur] == BLACK:
			stack.pop()
			new_strips = []
			for child in children[cur]:
				if leafs[child]:
					new_strips += [1]
				else:
					if len(strips[child]):
						strips[child][0] += 1
					new_strips += strips[child]
			new_strips.sort(reverse=True)
			strips[cur] = new_strips
			continue
		for child in E[cur]:
			if color[child] == BLACK:
				continue
			if color[child] == WHITE:
				color[child] = GRAY
				stack.append(child)
			children[cur].append(child)
		leafs[cur] = False if children[cur] else True
		color[cur] = BLACK
	return strips[root]

def solve(N, E, k):
	if k == 1:
		return 1
	if k == 2:
		return 2
	farthest_leaf = find_farthest_leaf(N, E)
	strips = search_strips(N, E, root=farthest_leaf)
	max_k = 1
	solution = 1
	for strip in strips:
		max_k += strip
		solution += 1
		if k <= max_k:
			return solution

def main():
	solutions = []
	for _ in range(int(input())):
		(n, k) = read_numbers()
		E = [[] for _ in range(n)]
		for _ in range(n - 1):
			(u, v) = read_numbers()
			u -= 1
			v -= 1
			E[u].append(v)
			E[v].append(u)
		solution = solve(n, E, k)
		solutions.append(str(solution))
	solutions = '\n'.join(solutions)
	output_line(solutions)
main()


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from collections import defaultdict
from sys import stdin, stdout
WHITE = 0
GRAY = 1
BLACK = 2
read_numbers = lambda : list(map(int, stdin.readline().strip().split()))
output_line = lambda x: stdout.write(x)

def find_farthest_leaf(N, E, root=0):
	color = [WHITE] * N
	parent = [0] * N
	dist = [0] * N
	max_dist = 0
	farthest_leaf = root
	color[root] = GRAY
	stack = [root]
	while stack:
		cur = stack[-1]
		if color[cur] == BLACK:
			stack.pop()
			continue
		for child in E[cur]:
			if color[child] == BLACK:
				continue
			if color[child] == WHITE:
				color[child] = GRAY
				stack.append(child)
			parent[child] = cur
			dist[child] = dist[parent[child]] + 1
			if dist[child] > max_dist:
				(max_dist, farthest_leaf) = (dist[child], child)
		color[cur] = BLACK
	return farthest_leaf

def search_strips(N, E, root):
	m = [WHITE] * N
	strips = [[] for _ in range(N)]
	c = [[] for _ in range(N)]
	leafs = [False] * N
	m[root] = GRAY
	stack = [root]
	while stack:
		cur = stack[-1]
		if m[cur] == BLACK:
			stack.pop()
			new_d = []
			for children in c[cur]:
				if leafs[children]:
					new_d += [1]
				else:
					if len(strips[children]) > 0:
						strips[children][0] += 1
					new_d += strips[children]
			strips[cur] = new_d
			strips[cur].sort(reverse=True)
			continue
		added = 0
		for i in E[cur]:
			if m[i] == WHITE:
				m[i] = GRAY
				stack.append(i)
				added += 1
			if m[i] != BLACK:
				c[cur].append(i)
		leafs[cur] = True if added == 0 else False
		m[cur] = BLACK
	return strips[root]

def solve(N, E, k):
	if k == 1:
		return 1
	if k == 2:
		return 2
	leaf = find_farthest_leaf(N, E)
	strips = search_strips(N, E, root=leaf)
	max_k = 1 + strips[0]
	if k <= max_k:
		return 2
	solution = 2
	for i in range(1, len(strips)):
		max_k += strips[i]
		solution += 1
		if k <= max_k:
			return solution

def main():
	solutions = []
	for _ in range(int(input())):
		(n, k) = read_numbers()
		E = [[] for _ in range(n)]
		for _ in range(n - 1):
			(u, v) = read_numbers()
			u -= 1
			v -= 1
			E[u].append(v)
			E[v].append(u)
		solution = solve(n, E, k)
		solutions.append(str(solution))
	solutions = '\n'.join(solutions)
	output_line(solutions)
main()


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from collections import defaultdict
from sys import stdin, stdout
WHITE = 0
GRAY = 1
BLACK = 2
read_numbers = lambda : list(map(int, stdin.readline().strip().split()))
output_line = lambda x: stdout.write(x)

def find_leaf(N, E, root=0):
	m = [WHITE] * N
	m[root] = GRAY
	s = [root]
	p = [0] * N
	d = [0] * N
	max_dist = 0
	max_index = 0
	while len(s):
		cur = s[-1]
		if m[cur] == BLACK:
			s.pop()
			continue
		for i in E[cur]:
			if m[i] == WHITE:
				m[i] = GRAY
				s.append(i)
				p[i] = cur
			if m[i] != BLACK:
				d[i] = d[p[i]] + 1
				if d[i] > max_dist:
					max_dist = d[i]
					max_index = i
		m[cur] = BLACK
	return max_index

def search(N, E, root):
	m = [WHITE] * N
	m[root] = GRAY
	s = [root]
	p = [0] * N
	d = [[] for _ in range(N)]
	c = [[] for _ in range(N)]
	leafs = [False] * N
	while len(s):
		cur = s[-1]
		if m[cur] == BLACK:
			s.pop()
			new_d = []
			for children in c[cur]:
				if leafs[children]:
					new_d += [1]
				else:
					if len(d[children]) > 0:
						d[children][0] += 1
					new_d += d[children]
			d[cur] = new_d
			d[cur].sort(reverse=True)
			continue
		added = 0
		for i in E[cur]:
			if m[i] == WHITE:
				m[i] = GRAY
				s.append(i)
				added += 1
				p[i] = cur
			if m[i] != BLACK:
				c[cur].append(i)
		leafs[cur] = True if added == 0 else False
		m[cur] = BLACK
	return d[root]

def solve(N, E, k):
	if k == 1:
		return 1
	if k == 2:
		return 2
	root = find_leaf(N, E)
	d = search(N, E, root)
	max_k = 1 + d[0]
	if k <= max_k:
		return 2
	s = 2
	for i in range(1, len(d)):
		max_k += d[i]
		s += 1
		if k <= max_k:
			return s

def main():
	solutions = []
	for _ in range(int(input())):
		(n, k) = read_numbers()
		E = defaultdict(list)
		for _ in range(n - 1):
			(u, v) = read_numbers()
			u -= 1
			v -= 1
			E[u].append(v)
			E[v].append(u)
		solutions.append(str(solve(n, E, k)))
	solutions = '\n'.join(solutions)
	output_line(solutions)
main()


def ConstructTree(AdjList, vertex):
	n = len(AdjList) - 1
	Colour = [0] * (n + 1)
	ToExplore = [0]
	Colour[0] = 1
	ToExplore.append(vertex)
	Colour[vertex] = 1
	pos = 1
	while pos <= n:
		node = ToExplore[pos]
		Colour[node] = 1
		pos += 1
		for u in AdjList[node]:
			if Colour[u] == 0:
				ToExplore.append(u)
	InfoList = [-1] * (n + 1)
	for i in range(n, -1, -1):
		node = ToExplore[i]
		height_below = 0
		child = 0
		for u in AdjList[node]:
			if InfoList[u] > height_below:
				height_below = InfoList[u]
				child = u
		InfoList[node] = height_below + 1
		InfoList[child] = -1
	a = 0
	b = n
	while a < b:
		if InfoList[a] == -1:
			if InfoList[b] != -1:
				InfoList[a] = InfoList[b]
				InfoList[b] = -1
				a += 1
			b -= 1
		else:
			a += 1
	if InfoList[a] == -1:
		a -= 1
	return InfoList[:a + 1]

def DiameterEnds(AdjList):
	l = len(AdjList)
	Colour = [0] * l
	ToExplore = []
	ToExplore.append(1)
	index = 1
	while len(ToExplore) != 0:
		node = ToExplore.pop(0)
		Colour[node] = 1
		index = node
		for u in AdjList[node]:
			if Colour[u] == 0:
				ToExplore.append(u)
	return index

def MinimumSubSetCover():
	(n, req) = list(map(int, input().split()))
	TreeRepresentation = []
	for _ in range(n + 1):
		TreeRepresentation.append([])
	for _ in range(n - 1):
		(u, v) = list(map(int, input().split()))
		TreeRepresentation[u].append(v)
		TreeRepresentation[v].append(u)
	if req == 1:
		return 1
	elif req == 2 or req == 3:
		return 2
	root = DiameterEnds(TreeRepresentation)
	RootedTree = ConstructTree(TreeRepresentation, root)
	RootedTree.sort(reverse=True)
	count = 1
	while req > 0:
		req -= RootedTree.pop(0)
		count += 1
	return count
testCases = int(input())
for _ in range(testCases):
	print(MinimumSubSetCover())


from collections import deque, Counter
import sys
sys.setrecursionlimit(1000000)

def helper(my_node):
	visited = [False for i in range(n)]
	depth = [0 for i in range(n)]
	max_depth(my_node, visited, depth)
	return depth

def max_depth(my_node, visited, depth):
	curr_depth = 0
	visited[my_node] = True
	q = []
	for i in G[my_node]:
		if visited[i] == False:
			visited[i] = True
			q.append(i)
	for i in q:
		curr_depth = max(max_depth(i, visited, depth), curr_depth)
	depth[my_node] = curr_depth + 1
	return curr_depth + 1
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	G = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		G[u - 1].append(v - 1)
		G[v - 1].append(u - 1)
	if k == 1:
		print(1)
	else:
		max_dist = -1
		max_node = -1
		visited = [False for i in range(n)]
		visited[0] = True
		q = deque()
		q.append((0, 0))
		while len(q) > 0:
			curr = q.popleft()
			curr_node = curr[0]
			curr_dist = curr[1]
			if curr_dist > max_dist:
				max_node = curr_node
				max_dist = curr_dist
			for i in range(len(G[curr_node])):
				if visited[G[curr_node][i]] == False:
					visited[G[curr_node][i]] = True
					q.append((G[curr_node][i], curr_dist + 1))
		depth = helper(max_node)
		cc = Counter(depth)
		c = 0
		ans = 1
		for i in range(n, -1, -1):
			br = False
			temp = cc[i] - cc[i + 1]
			for j in range(temp):
				ans += 1
				c += i
				if c >= k:
					br = True
					break
			if br:
				break
		print(ans)


import sys
sys.setrecursionlimit(10 ** 9)

def getFar(node, gr, n):
	done = [False] * (n + 1)
	fd = -1
	far = None
	qu = [(node, 0)]
	done[node] = True
	while qu:
		(nod, dis) = qu.pop(0)
		if fd < dis:
			fd = dis
			far = nod
		for cnod in gr[nod]:
			if done[cnod]:
				continue
			done[cnod] = True
			qu.append((cnod, dis + 1))
	return far

def fixHeight(nod, par, gr, H):
	isleaf = True
	for cnod in gr[nod]:
		if cnod == par:
			continue
		isleaf = False
		fixHeight(cnod, nod, gr, H)
		H[nod] = max(H[nod], 1 + H[cnod])
	if isleaf:
		H[nod] = 1

def dfs(nod, par, gr, H, li, cur):
	isleaf = True
	mx = 0
	for cnod in gr[nod]:
		if cnod == par:
			continue
		isleaf = False
		mx = max(mx, H[cnod])
	if isleaf:
		li.append(cur)
		return
	c = 0
	for cnod in gr[nod]:
		if cnod == par:
			continue
		if H[cnod] == mx and c == 0:
			dfs(cnod, nod, gr, H, li, cur + 1)
			c += 1
		else:
			dfs(cnod, nod, gr, H, li, 1)

def breakIntoLines(nod, par, gr, li, n, cur):
	H = [0] * (n + 1)
	fixHeight(nod, par, gr, H)
	dfs(nod, par, gr, H, li, 1)

def GETSOL(gr, n, k):
	if k == 1:
		return 1
	u = getFar(1, gr, n)
	li = []
	breakIntoLines(u, 0, gr, li, n, 1)
	li.sort(reverse=True)
	size = 1
	total = 0
	i = 0
	while total < k:
		size += 1
		total += li[i]
		i += 1
	return size
for case in range(int(input())):
	(n, k) = map(int, input().split())
	gr = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		gr[u].append(v)
		gr[v].append(u)
	chad = GETSOL(gr, n, k)
	print(chad)


import sys
sys.setrecursionlimit(10 ** 9)

def getFarthesting(node, gr, n1):
	do = [False] * (n1 + 1)
	fdrr = -1
	dur = None
	que = [(node, 0)]
	do[node] = True
	while que:
		(nod, dis) = que.pop(0)
		if fdrr < dis:
			fdrr = dis
			dur = nod
		for cnod in gr[nod]:
			if do[cnod]:
				continue
			do[cnod] = True
			que.append((cnod, dis + 1))
	return dur

def fixedHeight(nod, par, gr, H):
	isleaf = True
	for cnod in gr[nod]:
		if cnod == par:
			continue
		isleaf = False
		fixedHeight(cnod, nod, gr, H)
		H[nod] = max(H[nod], 1 + H[cnod])
	if isleaf:
		H[nod] = 1

def dfs(nod, par, gr, H, li, cur):
	isleaf = True
	mx = 0
	for cnod in gr[nod]:
		if cnod == par:
			continue
		isleaf = False
		mx = max(mx, H[cnod])
	if isleaf:
		li.append(cur)
		return
	c = 0
	for cnod in gr[nod]:
		if cnod == par:
			continue
		if H[cnod] == mx and c == 0:
			dfs(cnod, nod, gr, H, li, cur + 1)
			c += 1
		else:
			dfs(cnod, nod, gr, H, li, 1)

def breakIntoLines(nod, par, gr, li, n1, cur):
	H = [0] * (n1 + 1)
	fixedHeight(nod, par, gr, H)
	dfs(nod, par, gr, H, li, 1)

def GETSOLUTION(gr, n1, k):
	if k == 1:
		return 1
	u = getFarthesting(1, gr, n1)
	li = []
	breakIntoLines(u, 0, gr, li, n1, 1)
	li.sort(reverse=True)
	size1 = 1
	total1 = 0
	i = 0
	while total1 < k:
		size1 += 1
		total1 += li[i]
		i += 1
	return size1
for case in range(int(input())):
	(n1, k) = map(int, input().split())
	gr = [[] for i in range(n1 + 1)]
	for i in range(n1 - 1):
		(u1, v1) = map(int, input().split())
		gr[u1].append(v1)
		gr[v1].append(u1)
	chap = GETSOLUTION(gr, n1, k)
	print(chap)


import sys
try:
	sys.stdin = open('inputf.in', 'r')
	sys.stdout = open('outputf.in', 'w')
except:
	pass
from itertools import permutations, combinations
import heapq
from collections import OrderedDict
import bisect
from functools import cmp_to_key
from collections import deque
import string
from collections import Counter
from collections import defaultdict
from math import sqrt
from queue import PriorityQueue
import sys
from bisect import bisect_left, bisect_right
MOD = 1000000007
sys.setrecursionlimit(100000)

def ii():
	return int(sys.stdin.readline().strip())

def si():
	return sys.stdin.readline().strip()

def li():
	return list(map(int, sys.stdin.readline().strip().split()))

def mi():
	return map(int, sys.stdin.readline().strip().split())

def dparr(m, n):
	return [[0] * n for i in range(m)]

def disdp(dp):
	for i in dp:
		print(*i)

def gai(i):
	return ord(i) - ord('a')

def dij(graph, src):
	dis = [float('inf')] * (len(graph) + 1)
	dis[src] = 0
	q = deque()
	q.append(src)
	while len(q) > 0:
		x = q.popleft()
		for i in graph[x]:
			if dis[x] + 1 < dis[i]:
				dis[i] = min(dis[x] + 1, dis[i])
				q.append(i)
	return dis

def nsel(arr):
	pre = []
	st = [-1]
	for i in range(len(arr)):
		while len(st) > 0 and arr[i] <= arr[st[-1]]:
			st.pop()
		if len(st) == 0:
			pre.append(-1)
		else:
			pre.append(st[-1])
		st.append(i)
	return pre

def nser(arr):
	pre = []
	st = [-1]
	for i in range(len(arr) - 1, -1, -1):
		while len(st) > 0 and arr[i] <= arr[st[-1]]:
			st.pop()
		if len(st) == 0:
			pre.append(-1)
		else:
			pre.append(st[-1])
		st.append(i)
	return pre[::-1]

def getarea(arr):
	left = nsel(arr)
	right = nser(arr)
	n = len(arr)
	mx = 0
	print(left, right)
	for i in range(len(arr)):
		if left[i] == -1 and right[i] == -1:
			mx = max(mx, arr[i] * n)
		elif left[i] == -1 and right[i] != -1:
			mx = max(mx, arr[i] * right[i])
		elif left[i] != -1 and right[i] == -1:
			mx = max(mx, arr[i] * (n - left[i] - 1))
		else:
			mx = max(mx, arr[i] * (right[i] - left[i] - 1))
		print(mx)
	return mx

def func(nums, k):
	precnt = [1 if nums[0] % 2 != 0 else 0]
	n = len(nums)
	for i in range(1, n):
		if nums[i] % 2 != 0:
			precnt.append(1 + precnt[-1])
		else:
			precnt.append(precnt[-1])
	dp = {}
	dp[0] = 1
	ans = 0
	for i in range(n):
		if precnt[i] >= k:
			try:
				ans += dp[precnt[i] - k]
			except:
				pass
		try:
			dp[precnt[i]] += 1
		except:
			dp[precnt[i]] = 1
	print(ans)

def bfs(tree, n, node):
	vis = [False] * (n + 1)
	vis[node] = True
	q = deque()
	dist = [-1] * (n + 1)
	dist[node] = 0
	q.append(node)
	while len(q) > 0:
		x = q.popleft()
		for i in tree[x]:
			if vis[i] == False:
				dist[i] = dist[x] + 1
				vis[i] = True
				q.append(i)
	enddist = max(dist)
	endnode = dist.index(enddist)
	return (endnode, enddist)
dep = []
vis = []

def depth(tree, parent, start):
	if vis[start]:
		return 0
	vis[start] = True
	if tree[start] == []:
		dep[start] = 0
		return 0
	elif len(tree[start]) == 1 and tree[start][0] == parent:
		return 0
	else:
		md = 0
		for i in tree[start]:
			if i != start:
				md = max(md, depth(tree, start, i))
		dep[start] = md + 1
		return md + 1
final = {}

def get_path(tree, md, x, y, path):
	if vis[x]:
		return
	vis[x] = True
	if len(path) + 1 == md:
		final['path'] = path + [x]
		return
	for i in tree[x]:
		get_path(tree, md, i, y, path + [x])
t = ii()
for _ in range(t):
	(n, k) = mi()
	tree = {}
	for i in range(1, n + 1):
		tree[i] = []
	for i in range(n - 1):
		(u, v) = mi()
		tree[u].append(v)
		tree[v].append(u)
	if k == 1:
		print(1)
	else:
		(start, startdist) = bfs(tree, n, 1)
		(end, enddist) = bfs(tree, n, start)
		dep = [0] * (n + 1)
		vis = [False] * (n + 1)
		depth(tree, -1, start)
		vis = [False] * (n + 1)
		final = {}
		get_path(tree, max(dep) + 1, start, end, [])
		path = final['path']
		vispath = set(path)
		if k <= len(path):
			print(2)
		else:
			ans = 2
			currnode = len(path)
			dpdep = Counter()
			x = 0
			for i in range(n + 1):
				dpdep[i] = 0
			for i in range(1, len(dep)):
				if i in vispath:
					continue
				dpdep[dep[i]] += 1
			for i in range(n + 1, -1, -1):
				temp = dpdep[i] - x
				b = False
				for j in range(temp):
					ans += 1
					currnode += i + 1
					if currnode >= k:
						b = True
						break
				if b:
					break
				x += temp
			print(ans)


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(a, b, c, d, e, f):
	temp1 = True
	out = 0
	for i in c[a]:
		if i == b:
			continue
		temp1 = False
		out = max(out, d[i])
	if temp1:
		e.append(f)
		return
	c1 = 0
	for i in c[a]:
		if i == b:
			continue
		if d[i] == out and c1 == 0:
			dfs(i, a, c, d, e, f + 1)
			c1 += 1
		else:
			dfs(i, a, c, d, e, 1)

def h(a, b, c, d):
	temp1 = True
	for i in c[a]:
		if i == b:
			continue
		temp1 = False
		h(i, a, c, d)
		d[a] = max(d[a], 1 + d[i])
	if temp1:
		d[a] = 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	temp = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		temp[u].append(v)
		temp[v].append(u)
	if k == 1:
		print(1)
	else:
		flag = [False] * (n + 1)
		flag[1] = True
		sub = [(1, 0)]
		last = None
		neg = -1
		while sub:
			(a, b) = sub.pop(0)
			if neg < b:
				neg = b
				last = a
			for k1 in temp[a]:
				if flag[k1]:
					continue
				flag[k1] = True
				sub.append((k1, b + 1))
		arr = []
		H = [0] * (n + 1)
		h(last, 0, temp, H)
		dfs(last, 0, temp, H, arr, 1)
		arr.sort(reverse=True)
		ans = 1
		(t1, t2) = (0, 0)
		while t1 < k:
			ans += 1
			t1 += arr[t2]
			t2 += 1
		print(ans)


import sys
import math
from collections import *
from queue import *
from bisect import *
sys.setrecursionlimit(10 ** 5)
MOD = int(1000000000.0 + 7)
inf = float('inf')
ninf = float('-inf')
input = sys.stdin.readline

def ii():
	return list(map(int, input().strip().split()))
(G, H, li) = ([], [], [])

def getFar(node, n):
	vis = [False for k in range(n + 1)]
	(vis[node], far) = (True, 1)
	qu = Queue()
	qu.put(far)
	while not qu.empty():
		parentIndex = qu.get()
		for itrNode in G[parentIndex]:
			if not vis[itrNode]:
				vis[itrNode] = True
				qu.put(itrNode)
				far = itrNode
	return far

def f(node, parent, current, maxm):
	c = False
	for itrNode in G[node]:
		if itrNode != parent:
			if H[itrNode] == maxm and c == False:
				dfs(itrNode, node, current + 1)
				c = True
			else:
				dfs(itrNode, node, 1)

def dfs(nod, parent, current):
	(checkLeaf, maxm) = (True, 0)
	for itrNode in G[nod]:
		if itrNode != parent:
			(checkLeaf, maxm) = (False, max(maxm, H[itrNode]))
	if checkLeaf:
		li.append(current)
		return
	else:
		f(nod, parent, current, maxm)

def fixHeight(nod, parent):
	checkLeaf = True
	for itrNode in G[nod]:
		if itrNode != parent:
			checkLeaf = False
			fixHeight(itrNode, nod)
			H[nod] = max(H[nod], 1 + H[itrNode])
	if checkLeaf:
		H[nod] = 1

def breakIntoLines(nod, parent, n):
	fixHeight(nod, parent)
	dfs(nod, parent, 1)

def getSol(n, k):
	if k == 1:
		return 1
	u = getFar(1, n)
	(size, total, i) = (1, 0, 0)
	breakIntoLines(u, 0, n)
	li.sort(reverse=True)
	while total < k:
		size += 1
		total += li[i]
		i += 1
	return size
for _ in range(int(input())):
	(n, k) = ii()
	G = [[] for j in range(n + 1)]
	for j in range(n - 1):
		(u, v) = ii()
		G[u].append(v)
		G[v].append(u)
	H = [0] * (n + 1)
	print(getSol(n, k))
	G.clear()
	H.clear()
	li.clear()


import sys
sys.setrecursionlimit(10 ** 9)

def atLast(vert, adj, n):
	q = n
	while q < n:
		pass

def getLast(vert, adj, n):
	ok = [False] * (n + 1)
	ld = -1
	dist = None
	qu = [(vert, 0)]
	ok[vert] = True
	while qu:
		(cod, dis) = qu.pop(0)
		if ld < dis:
			ld = dis
			dist = cod
		for ver in adj[cod]:
			if ok[ver]:
				continue
			ok[ver] = True
			qu.append((ver, dis + 1))
	return dist

def atH(cod, par, adj, H):
	leaf = True
	for ver in adj[cod]:
		if ver == par:
			continue
		leaf = False
		atH(ver, cod, adj, H)
		H[cod] = max(H[cod], 1 + H[ver])
	if leaf:
		H[cod] = 1

def atFirst(cod, par):
	if cod > 10:
		n = cod
		while n < par:
			n << 1

def dfs(cod, par, adj, H, li, cur):
	leaf = True
	mx = 0
	for ver in adj[cod]:
		if ver == par:
			continue
		leaf = False
		mx = max(mx, H[ver])
	if leaf:
		li.append(cur)
		return
	c = 0
	for ver in adj[cod]:
		if ver == par:
			continue
		if H[ver] == mx and c == 0:
			dfs(ver, cod, adj, H, li, cur + 1)
			c += 1
		else:
			dfs(ver, cod, adj, H, li, 1)

def getLine(cod, par, adj, li, n, cur):
	H = [0] * (n + 1)
	atH(cod, par, adj, H)
	dfs(cod, par, adj, H, li, 1)

def solve(adj, n, k):
	if k == 1:
		atFirst(10, 5)
		return 1
	u = getLast(1, adj, n)
	li = []
	getLine(u, 0, adj, li, n, 1)
	li.sort(reverse=True)
	len = 1
	sum = 0
	i = 0
	while sum < k:
		len += 1
		sum += li[i]
		i += 1
	return len
for case in range(int(input())):
	(n, k) = map(int, input().split())
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	ans = solve(adj, n, k)
	print(ans)


import sys
sys.setrecursionlimit(10 ** 9)

def getFarthest(node, getright, n):
	done = [False] * (n + 1)
	fd = -1
	far = None
	qu = [(node, 0)]
	done[node] = True
	while qu:
		(nod, dis) = qu.pop(0)
		if fd < dis:
			fd = dis
			far = nod
		for cnod in getright[nod]:
			if done[cnod]:
				continue
			done[cnod] = True
			qu.append((cnod, dis + 1))
	return far

def correctHeight(nod, par, getright, height):
	isleaf = True
	for cnod in getright[nod]:
		if cnod == par:
			continue
		isleaf = False
		correctHeight(cnod, nod, getright, height)
		height[nod] = max(height[nod], 1 + height[cnod])
	if isleaf:
		height[nod] = 1

def dfs(nod, par, getright, height, leaf, curentNode):
	isleaf = True
	mx = 0
	for cnod in getright[nod]:
		if cnod == par:
			continue
		isleaf = False
		mx = max(mx, height[cnod])
	if isleaf:
		leaf.append(curentNode)
		return
	c = 0
	for cnod in getright[nod]:
		if cnod == par:
			continue
		if height[cnod] == mx and c == 0:
			dfs(cnod, nod, getright, height, leaf, curentNode + 1)
			c += 1
		else:
			dfs(cnod, nod, getright, height, leaf, 1)

def convertintolevels(nod, par, getright, leaf, n, curentNode):
	height = [0] * (n + 1)
	correctHeight(nod, par, getright, height)
	dfs(nod, par, getright, height, leaf, 1)

def minimumsubtreecover(getright, n, k):
	if k == 1:
		return 1
	u = getFarthest(1, getright, n)
	leaf = []
	convertintolevels(u, 0, getright, leaf, n, 1)
	leaf.sort(reverse=True)
	size = 1
	totalsum = 0
	i = 0
	while totalsum < k:
		size += 1
		totalsum += leaf[i]
		i += 1
	return size
for case in range(int(input())):
	(n, k) = map(int, input().split())
	getright = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		getright[u].append(v)
		getright[v].append(u)
	finalans = minimumsubtreecover(getright, n, k)
	print(finalans)


import sys
sys.setrecursionlimit(10 ** 9)

def getData(node1, gr, n):
	arr = [False] * (n + 1)
	x = -1
	far = None
	q = [(node1, 0)]
	arr[node1] = True
	while q:
		(node2, dis) = q.pop(0)
		if x < dis:
			x = dis
			far = node2
		for cnod in gr[node2]:
			if arr[cnod]:
				continue
			arr[cnod] = True
			q.append((cnod, dis + 1))
	return far

def getData2(node, par, gr, H):
	isleaf = True
	for cnod in gr[node]:
		if cnod == par:
			continue
		isleaf = False
		getData2(cnod, node, gr, H)
		H[node] = max(H[node], 1 + H[cnod])
	if isleaf:
		H[node] = 1

def dfs(node, par, gr, H, li, cur):
	isleaf = True
	mx = 0
	for cnod in gr[node]:
		if cnod == par:
			continue
		isleaf = False
		mx = max(mx, H[cnod])
	if isleaf:
		li.append(cur)
		return
	c = 0
	for cnod in gr[node]:
		if cnod == par:
			continue
		if H[cnod] == mx and c == 0:
			dfs(cnod, node, gr, H, li, cur + 1)
			c += 1
		else:
			dfs(cnod, node, gr, H, li, 1)

def getLines(node, par, gr, li, n, cur):
	H = [0] * (n + 1)
	getData2(node, par, gr, H)
	dfs(node, par, gr, H, li, 1)

def getData3(gr, n, k):
	if k == 1:
		return 1
	u = getData(1, gr, n)
	li = []
	getLines(u, 0, gr, li, n, 1)
	li.sort(reverse=True)
	size = 1
	total = 0
	i = 0
	while total < k:
		size += 1
		total += li[i]
		i += 1
	return size
for i in range(int(input())):
	(n, k) = map(int, input().split())
	gr = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		gr[u].append(v)
		gr[v].append(u)
	min_subset = getData3(gr, n, k)
	print(min_subset)


import sys
sys.setrecursionlimit(10 ** 9)
import copy

def dfs(start, points, visited, subtree_nodes):
	visited[start] = True
	for i in points[start]:
		if not visited[i]:
			subtree_nodes[start] = max(subtree_nodes[start], dfs(i, points, visited, subtree_nodes))
	subtree_nodes[start] += 1
	return subtree_nodes[start]

def dfs2(start, top_node, points, visited, subtree_nodes, counter, ans_list):
	visited[start] = True
	if subtree_nodes[start] == 1 and start != top_node:
		ans_list.append(counter)
		return None
	correct_neighbour = -1
	correct_sum = -1
	for i in points[start]:
		if not visited[i]:
			if subtree_nodes[i] > correct_sum:
				correct_neighbour = i
				correct_sum = subtree_nodes[i]
	dfs2(correct_neighbour, top_node, points, visited, subtree_nodes, counter + 1, ans_list)
	for i in points[start]:
		if not visited[i] and i != correct_neighbour:
			dfs2(i, top_node, points, visited, subtree_nodes, 1, ans_list)
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	points = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = [int(i) for i in input().split()]
		points[u - 1].append(v - 1)
		points[v - 1].append(u - 1)
	if k == 1:
		print(1)
		continue
	points2 = copy.deepcopy(points)
	stack = []
	visited = [False for i in range(n)]
	stack.append(0)
	visited[0] = True
	top_node = 0
	max_height = 1
	while stack:
		current = stack[-1]
		if points[current]:
			neighbour = points[current].pop()
			if not visited[neighbour]:
				stack.append(neighbour)
				visited[neighbour] = True
				if len(stack) > max_height:
					max_height = len(stack)
					top_node = stack[-1]
		else:
			stack.pop()
	subtree_nodes = [0 for i in range(n)]
	visited = [False for i in range(n)]
	dfs(top_node, points2, visited, subtree_nodes)
	if subtree_nodes[top_node] >= k:
		print(2)
		continue
	ans_list = []
	visited = [False for i in range(n)]
	dfs2(top_node, top_node, points2, visited, subtree_nodes, 1, ans_list)
	ans_list.sort(reverse=True)
	sum_ = 0
	for i in range(len(ans_list)):
		sum_ += ans_list[i]
		if sum_ >= k:
			print(i + 2)
			break


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(a, b, y, arr2, arr3, n1):
	check = True
	tmp_var = 0
	for j in y[a]:
		if j == b:
			continue
		check = False
		tmp_var = max(tmp_var, arr2[j])
	if check:
		arr3.append(n1)
		return
	tmp = 0
	for j in y[a]:
		if j == b:
			continue
		if tmp == 0 and arr2[j] == tmp_var:
			dfs(j, a, y, arr2, arr3, n1 + 1)
			tmp = tmp + 1
		else:
			dfs(j, a, y, arr2, arr3, 1)

def ver_edg(a, b, arr2, y):
	check = True
	for j in y[a]:
		if j == b:
			continue
		check = False
		ver_edg(j, a, arr2, y)
		arr2[a] = max(arr2[j] + 1, arr2[a])
	if check:
		arr2[a] = 1

def calculate(a, b, y, arr3, z, n1):
	arr2 = [0] * (z + 1)
	ver_edg(a, b, arr2, y)
	dfs(a, b, y, arr2, arr3, 1)

def solve1(x, y, z):
	arr1 = [False] * (z + 1)
	x1 = -1
	y1 = None
	z1 = [(x, 0)]
	arr1[x] = True
	while z1:
		(a, x2) = z1.pop(0)
		if x1 < x2:
			x1 = x2
			y1 = a
		for j in y[a]:
			if arr1[j]:
				continue
			arr1[j] = True
			z1.append((j, x2 + 1))
	return y1

def solve(y, z, temp):
	if temp == 1:
		return 1
	inp = solve1(1, y, z)
	arr3 = []
	calculate(inp, 0, y, arr3, z, 1)
	arr3.sort(reverse=True)
	t1 = 1
	t2 = 0
	i = 0
	while t2 < temp:
		t1 = t1 + 1
		t2 = t2 + arr3[i]
		i = i + 1
	return t1
for ii in range(int(input())):
	(z, temp) = map(int, input().split())
	y = [[] for i in range(z + 1)]
	for i in range(z - 1):
		(inp, v) = map(int, input().split())
		y[inp].append(v)
		y[v].append(inp)
	result = solve(y, z, temp)
	print(result)


import sys
sys.setrecursionlimit(100000000)

def minimum_subtree_cover():
	(n, k) = map(int, input().split())
	tree = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		addEdge(tree, u, v)
	ans = calc_min_size_subset(tree, n, k)
	print(ans)

def addEdge(tree, u, v):
	tree[u].append(v)
	tree[v].append(u)

def calc_min_size_subset(tree, n, k):
	if k == 1:
		return 1
	u = get_cur(1, tree, n)
	store = []
	seperate_edges(u, 0, tree, store, n)
	ans = 1
	total = 0
	i = 0
	store.sort(reverse=True)
	while total < k:
		ans += 1
		total += store[i]
		i += 1
	return ans

def get_cur(node, tree, n):
	visited = [False] * (n + 1)
	fd = -1
	visited[node] = True
	visited_list = [[node, 0]]
	while len(visited_list) != 0:
		item = visited_list[0]
		visited_list.pop(0)
		nod = item[0]
		dis = item[1]
		if fd < dis:
			fd = dis
			cur = nod
		for element in tree[nod]:
			if visited[element]:
				continue
			visited[element] = True
			visited_list.append([element, dis + 1])
	return cur

def seperate_edges(nod, parent_node, tree, store, n):
	point = [0] * (n + 1)
	find_height(nod, parent_node, tree, point)
	depth_first_search(nod, parent_node, tree, point, store, 1)

def depth_first_search(nod, parent_node, tree, point, store, cur):
	isLastNode = True
	mx = 0
	for element in tree[nod]:
		if element != parent_node:
			isLastNode = False
			mx = max(mx, point[element])
	if isLastNode:
		store.append(cur)
		return
	c = 0
	for element in tree[nod]:
		if element == parent_node:
			continue
		if point[element] == mx and c == 0:
			depth_first_search(element, nod, tree, point, store, cur + 1)
			c += 1
		else:
			depth_first_search(element, nod, tree, point, store, 1)

def find_height(nod, parent_node, tree, point):
	isLastNode = True
	for element in tree[nod]:
		if element == parent_node:
			continue
		isLastNode = False
		find_height(element, nod, tree, point)
		point[nod] = max(point[nod], 1 + point[element])
	if isLastNode:
		point[nod] = 1
T = int(input())
for _ in range(T):
	minimum_subtree_cover()


import sys
sys.setrecursionlimit(100000)

def calc_far(node, G, n):
	done = [False] * (n + 1)
	fd = -1
	done[node] = True
	queue = []
	queue.append([node, 0])
	while len(queue) != 0:
		pi = queue[0]
		queue.pop(0)
		nod = pi[0]
		dis = pi[1]
		if fd < dis:
			fd = dis
			far = nod
		for cnod in G[nod]:
			if done[cnod]:
				continue
			done[cnod] = True
			queue.append([cnod, dis + 1])
	return far

def dfs(nod, par, G, H, li, cur):
	isleaf = True
	mx = 0
	for cnod in G[nod]:
		if cnod != par:
			isleaf = False
			mx = max(mx, H[cnod])
	if isleaf:
		li.append(cur)
		return
	c = 0
	for cnod in G[nod]:
		if cnod == par:
			continue
		if H[cnod] == mx and c == 0:
			dfs(cnod, nod, G, H, li, cur + 1)
			c += 1
		else:
			dfs(cnod, nod, G, H, li, 1)

def fixheight(nod, par, G, H):
	isleaf = True
	for cnod in G[nod]:
		if cnod == par:
			continue
		isleaf = False
		fixheight(cnod, nod, G, H)
		H[nod] = max(H[nod], 1 + H[cnod])
	if isleaf:
		H[nod] = 1

def breakintolines(nod, par, G, li, n):
	H = [0] * (n + 1)
	fixheight(nod, par, G, H)
	dfs(nod, par, G, H, li, 1)

def calc_ans(gr, n, k):
	if k == 1:
		return 1
	u = calc_far(1, gr, n)
	li = []
	breakintolines(u, 0, gr, li, n)
	li.sort(reverse=True)
	size = 1
	total = 0
	i = 0
	while total < k:
		size += 1
		total += li[i]
		i += 1
	return size
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	gr = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		gr[u].append(v)
		gr[v].append(u)
	ans = calc_ans(gr, n, k)
	print(ans)


def farNode(root, tree):
	d = [False] * (len(tree) + 1)
	fNode = (root, -1)
	q = [(root, 0)]
	while q:
		(node, dist) = q.pop(0)
		d[node] = True
		fNode = (node, dist) if dist > fNode[1] else fNode
		for cNode in tree[node]:
			if not d[cNode]:
				q.append((cNode, dist + 1))
	return fNode[0]

def leafNodes(root, tree, parentList, leafList):
	d = [False] * (len(tree) + 1)
	q = [(root, 0)]
	while q:
		isLeaf = True
		(node, dist) = q.pop()
		d[node] = True
		for cNode in tree[node]:
			if not d[cNode]:
				q.append((cNode, dist + 1))
				parentList[cNode] = node
				isLeaf = False
		if isLeaf:
			leafList.append((node, dist))

def maxContributors(root, parentList, leafList):
	optedOut = [False] * (len(parentList) + 1)
	optedOut[root] = True
	contributors = []
	leafList.sort(key=lambda x: x[1], reverse=True)
	for leaf in leafList:
		parent = parentList[leaf[0]]
		c = 1
		while not optedOut[parent]:
			optedOut[parent] = True
			c += 1
			parent = parentList[parent]
		contributors.append(c)
	contributors.sort(reverse=True)
	return contributors
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	tree = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		tree[u].append(v)
		tree[v].append(u)
	if k == 1:
		print(1)
		continue
	fNode = farNode(1, tree)
	parentList = [None] * (n + 1)
	leafList = []
	leafNodes(fNode, tree, parentList, leafList)
	cont = maxContributors(fNode, parentList, leafList)
	s = 1
	i = 0
	while k > 1:
		s += 1
		k -= cont[i]
		i += 1
	print(s)


from collections import defaultdict
import queue
import sys
sys.setrecursionlimit(150000)

def getFar(node, n):
	done = [False] * (n + 1)
	fd = -1
	done[node] = True
	qu = queue.Queue()
	qu.put((node, 0))
	while not qu.empty():
		pi = qu.get()
		(nod, dis) = (pi[0], pi[1])
		if fd < dis:
			fd = dis
			far = nod
		for cnod in tree[nod]:
			if done[cnod]:
				continue
			done[cnod] = True
			qu.put((cnod, dis + 1))
	return far

def dfs(nod, par, H, li, cur):
	isleaf = True
	mx = 0
	for cnod in tree[nod]:
		if cnod != par:
			isleaf = False
			mx = max(mx, H[cnod])
	if isleaf:
		li.append(cur)
		return
	c = 0
	for cnod in tree[nod]:
		if cnod == par:
			continue
		if H[cnod] == mx and c == 0:
			dfs(cnod, nod, H, li, cur + 1)
			c += 1
		else:
			dfs(cnod, nod, H, li, 1)

def fixheight(nod, par, H):
	isleaf = True
	for cnod in tree[nod]:
		if cnod == par:
			continue
		isleaf = False
		fixheight(cnod, nod, H)
		H[nod] = max(H[nod], 1 + H[cnod])
	if isleaf:
		H[nod] = 1

def breakIntolines(nod, par, li, n):
	H = [0] * (n + 1)
	try:
		fixheight(nod, par, H)
	except:
		print(3)
	dfs(nod, par, H, li, 1)

def solve(n, k):
	if k == 1:
		return 1
	u = getFar(1, n)
	li = []
	breakIntolines(u, 0, li, n)
	li.sort(reverse=True)
	size = 1
	total = 0
	i = 0
	while total < k:
		size += 1
		total += li[i]
		i += 1
	return size
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split())
	tree = defaultdict(list)
	for _ in range(n - 1):
		(a, b) = map(int, input().strip().split())
		tree[a].append(b)
		tree[b].append(a)
	print(solve(n, k))


import sys
sys.setrecursionlimit(10 ** 9)

def dfscall(ver, xx, edge, dis, lenn, cur):
	leaf = True
	maxx = 0
	for nod in edge[ver]:
		if nod == xx:
			continue
		(leaf, maxx) = (False, max(maxx, dis[nod]))
	if leaf:
		lenn.append(cur)
		return
	c = 0
	for nod in edge[ver]:
		if nod == xx:
			continue
		if dis[nod] == maxx and c == 0:
			dfscall(nod, ver, edge, dis, lenn, cur + 1)
			c += 1
		else:
			dfscall(nod, ver, edge, dis, lenn, 1)

def distance(ver, xx, edge, dis):
	leaf = True
	for nod in edge[ver]:
		if nod == xx:
			continue
		leaf = False
		distance(nod, ver, edge, dis)
		dis[ver] = max(dis[ver], 1 + dis[nod])
	if leaf:
		dis[ver] = 1
for i in range(int(input())):
	(n, k) = map(int, input().split())
	edge = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		edge[u].append(v)
		edge[v].append(u)
	if k == 1:
		print(1)
	else:
		arr = [False] * (n + 1)
		(x, u, queue, arr[1]) = (-1, None, [(1, 0)], True)
		while queue:
			(node2, dis) = queue.pop(0)
			if x < dis:
				(x, u) = (dis, node2)
			for nod in edge[node2]:
				if arr[nod]:
					continue
				arr[nod] = True
				queue.append((nod, dis + 1))
		(lenn, dis) = ([], [0] * (n + 1))
		distance(u, 0, edge, dis)
		dfscall(u, 0, edge, dis, lenn, 1)
		lenn.sort(reverse=True)
		(size, total, i) = (1, 0, 0)
		while total < k:
			size += 1
			total += lenn[i]
			i += 1
		print(size)


import sys
sys.setrecursionlimit(10 ** 9)

def getValue(node1, graph, n):
	(myx, far) = (-1, None)
	myarr = [0] * (n + 1)
	qry = [(node1, 0)]
	myarr[node1] = 1
	while qry:
		(node2, dist) = qry.pop(0)
		if myx < dist:
			(myx, far) = (dist, node2)
		for cpt in graph[node2]:
			if myarr[cpt]:
				continue
			myarr[cpt] = 1
			qry.append((cpt, dist + 1))
	return far

def getValue2(pt, mypar, graph, myH):
	checkleaf = 1
	for cpt in graph[pt]:
		if cpt == mypar:
			continue
		checkleaf = 0
		getValue2(cpt, pt, graph, myH)
		myH[pt] = max(myH[pt], 1 + myH[cpt])
	if checkleaf:
		myH[pt] = 1

def mydfs(pt, mypar, graph, myH, li, current):
	(checkleaf, mymx) = (1, 0)
	for cpt in graph[pt]:
		if cpt == mypar:
			continue
		checkleaf = 5 - 5
		mymx = max(mymx, myH[cpt])
	if checkleaf:
		li.append(current)
		return
	c = 5 - 5
	for cpt in graph[pt]:
		if cpt == mypar:
			continue
		if myH[cpt] == mymx and c == 0:
			mydfs(cpt, pt, graph, myH, li, current + 1)
			c = c + 1
		else:
			mydfs(cpt, pt, graph, myH, li, 1)

def getPaths(pt, mypar, graph, li, n, current):
	myH = [0] * (n + 1)
	getValue2(pt, mypar, graph, myH)
	mydfs(pt, mypar, graph, myH, li, 1)

def getValue3(graph, n, k):
	if k == 1:
		return 5 - 4
	u = getValue(1, graph, n)
	li = list()
	getPaths(u, 0, graph, li, n, 1)
	li = sorted(li, reverse=1)
	(size, total, loop) = (1, 0, 0)
	while total < k:
		total = total + li[loop]
		size = size + 1
		loop = loop + 1
	return size

def solve():
	(n, k) = list(map(int, input().split()))
	graph = [list() for loop in range(n + 1)]
	for loop in range(n - 1):
		(u, v) = list(map(int, input().split()))
		graph[v].append(u)
		graph[u].append(v)
	temp = getValue3(graph, n, k)
	sys.stdout.write(str(temp) + '\n')

def main():
	global t
	tc = int(input())
	for t in range(tc):
		solve()
main()


import sys
sys.setrecursionlimit(10 ** 9)

def get_farest_node(node1, graph, n):
	arr = [False] * (n + 1)
	x = -1
	far = None
	q = [(node1, 0)]
	arr[node1] = True
	while q:
		(node2, dis) = q.pop(0)
		if x < dis:
			x = dis
			far = node2
		for cnod in graph[node2]:
			if arr[cnod]:
				continue
			arr[cnod] = True
			q.append((cnod, dis + 1))
	return far

def get_node1(node, par, graph, H):
	check_leaf = True
	for cnod in graph[node]:
		if cnod == par:
			continue
		check_leaf = False
		get_node1(cnod, node, graph, H)
		H[node] = max(H[node], 1 + H[cnod])
	if check_leaf:
		H[node] = 1

def direct_search(node, par, graph, H, li, cur):
	check_leaf = True
	mx = 0
	for cnod in graph[node]:
		if cnod == par:
			continue
		check_leaf = False
		mx = max(mx, H[cnod])
	if check_leaf:
		li.append(cur)
		return
	c = 0
	for cnod in graph[node]:
		if cnod == par:
			continue
		if H[cnod] == mx and c == 0:
			direct_search(cnod, node, graph, H, li, cur + 1)
			c += 1
		else:
			direct_search(cnod, node, graph, H, li, 1)

def findLines_(node, par, graph, li, n, cur):
	H = [0] * (n + 1)
	get_node1(node, par, graph, H)
	direct_search(node, par, graph, H, li, 1)
for i in range(int(input())):
	(n, k) = map(int, input().split())
	graph = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		graph[x].append(y)
		graph[y].append(x)
	if k == 1:
		size = 1
	else:
		x = get_farest_node(1, graph, n)
		li = []
		findLines_(x, 0, graph, li, n, 1)
		li.sort(reverse=True)
		size = 1
		total = 0
		i = 0
		while total < k:
			size += 1
			total += li[i]
			i += 1
	min_subset = size
	print(min_subset)


import sys
sys.setrecursionlimit(10 ** 6)

def e(a, b):
	return [i for i in a if i not in b]

def dfs(r):
	(v, s, c) = (set(), [r], 0)
	while s:
		u = s.pop()
		c += 1
		if u not in v:
			v.add(u)
			s.extend(e(d[u], v))
			if not e(d[u], v):
				f[u] = c
				c = 0

def a(u=1, v=0):
	if not e(d[u], {v}):
		depth[u] = 0
		return 0
	else:
		depth[u] = 1 + max([a(i, u) for i in e(d[u], {v})])
		return depth[u]
T = int(input())
for n1 in range(T):
	(n, k) = [int(i) for i in input().split(' ')]
	d = dict()
	for i in range(1, n + 1):
		d[i] = set()
	for i in range(n - 1):
		(u, v) = [int(i) for i in input().split(' ')]
		d[u].add(v)
		d[v].add(u)
	if k == 1:
		print(1)
		continue
	f = dict()
	depth = dict()
	a()
	for i in d:
		d[i] = sorted(d[i], key=lambda x: depth[x])
	r = d[1][-1]
	while depth[r] != 0:
		r = d[r][-2]
	a(r)
	for i in d:
		d[i] = sorted(d[i], key=lambda x: depth[x])
	dfs(r)
	l = sorted(list(f.values()))
	i = 0
	while n >= k:
		n -= l[i]
		i += 1
	print(len(l) - i + 2)


from sys import stdin, stdout
import math
from collections import defaultdict, deque
import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, -1))
sys.setrecursionlimit(10 ** 7)

class Dfs:

	def __init__(self, d, n):
		self.d = d
		self.n = n

	def dfs(self, start=1):
		(q, parent) = (deque([start]), [0] * (self.n + 1))
		parent[start] = 1
		while q:
			node = q.popleft()
			for x in self.d[node]:
				if parent[x] == 0:
					parent[x] = node
					q.appendleft(x)
		return parent

	def dfs_further(self, start=1):
		height = [-1] * (self.n + 1)
		(ma, Node_last, height[start], q) = (0, -1, 0, deque([start]))
		while q:
			node = q.popleft()
			for x in self.d[node]:
				if height[x] == -1:
					height[x] = height[node] + 1
					if height[x] > ma:
						(ma, Node_last) = (height[x], x)
					q.appendleft(x)
		return [Node_last, ma]

	def tree_diameter(self):
		z = self.dfs_further()
		far_node = z[0]
		z1 = self.dfs_further(start=far_node)
		tree_length = z1[1]
		return [tree_length + 1, z1[0], z[0]]

def DFS1(st, end):
	q = deque([st])
	parent = [-1] * (n + 1)
	parent[st] = st
	high[st] = 0
	mx = 0
	while q:
		node = q.popleft()
		cnt = 0
		for x in d[node]:
			if parent[x] == -1:
				cnt += 1
				high[x] = high[node] + 1
				mx = max(high[x], mx)
				parent[x] = node
				q.append(x)
		if cnt == 0:
			leaf_node.add(node)
	e = end
	while e != st:
		visit[e] = True
		e = parent[e]
	visit[e] = True

def main():
	try:
		global lo, n, ans, k, visit, d, dp, tin, tout, high, leaf_node
		(n, k) = In()
		leaf_node = set()
		ans = [float('inf')]
		d = defaultdict(list)
		for i in range(n - 1):
			(a, b) = In()
			d[a].append(b)
			d[b].append(a)
		if k == 1:
			print(1)
			return
		dfs1 = Dfs(d, n)
		s = set()
		an = dfs1.tree_diameter()
		s.add(an[1])
		s.add(an[2])
		visit = [False] * (n + 1)
		high = [-1] * (n + 1)
		DFS1(an[1], an[2])
		for x in s:
			if x in leaf_node:
				leaf_node.remove(x)
		ans = 2
		cnt = an[0]
		if an[0] >= k:
			print(2)
			return
		l = []
		pants = [(high[x], x) for x in leaf_node]
		pants.sort(key=lambda x: x[0], reverse=True)
		for pant in pants:
			x = pant[1]
			cnt1 = 0
			q = deque([x])
			while q:
				node = q.popleft()
				if visit[node]:
					continue
				visit[node] = True
				cnt1 += 1
				cur = high[node]
				topush = -1
				for v in d[node]:
					if not visit[v] and high[v] < cur:
						cur = high[v]
						topush = v
				if topush != -1:
					q.append(topush)
			if cnt1:
				l.append((cnt1, x))
		l.sort(key=lambda x: x[0], reverse=True)
		for x in l:
			cnt += x[0]
			ans += 1
			if cnt >= k:
				break
		print(ans)
	except:
		pass

def add(a, b, c):
	res = a + b
	if res >= c:
		return res - c
	else:
		return res

def mod(a, b, c):
	res = a * b
	if res >= c:
		return res % c
	else:
		return res

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	w = a // gcd(a, b)
	return w * b

def expo(a, b):
	(x, y) = (1, a)
	while b > 0:
		if b & 1:
			x = x * y
		y = y * y
		b >>= 1
	return x

def power(a, b, m):
	(x, y) = (1,)
	while b > 0:
		if b & 1:
			x = mod(x, y, m)
		y = mod(y, y, m)
		b >>= 1
	return x

def L():
	return list(map(int, stdin.readline().split()))

def In():
	return map(int, stdin.readline().split())

def I():
	return int(stdin.readline())
P = 1000000007
for _ in range(I()):
	main()


import heapq

class maxq:

	def heappush(h, key, val):
		heapq.heappush(h, (-key, val))

	def heappop(h):
		(key, val) = heapq.heappop(h)
		return val

def get_subtrees_rooted_on_path(tree, path):
	subtrees = []
	for i in range(len(path)):
		current = path[i]
		prev = None if i == 0 else path[i - 1]
		next = None if i + 1 == len(path) else path[i + 1]
		for neighbor in tree[current]:
			if neighbor != prev and neighbor != next:
				subtrees += [(current, neighbor)]
	return subtrees

def get_heaviest_leaves(tree, subtree_root):
	(tree_source, root) = subtree_root
	values = {root: 1}
	path_from_root = {root: None}
	next = [root]
	heaviest_leaves = []
	distance = 0
	while len(next) > 0:
		current = next
		next = []
		distance += 1
		for node in current:
			is_leaf = True
			for next_node in tree[node]:
				if next_node == tree_source:
					continue
				if next_node in values:
					continue
				next += [next_node]
				values[next_node] = distance + 1
				path_from_root[next_node] = node
				is_leaf = False
			if is_leaf:
				maxq.heappush(heaviest_leaves, values[node], (values[node], node))
	taken = set()
	while len(heaviest_leaves) > 0:
		(weight, heaviest_leaf) = maxq.heappop(heaviest_leaves)
		valid = True
		node = heaviest_leaf
		while path_from_root[node] is not None:
			prev = node
			node = path_from_root[node]
			if node in taken:
				if weight == values[heaviest_leaf] - values[node]:
					break
				valid = False
				weight = values[heaviest_leaf] - values[node]
				maxq.heappush(heaviest_leaves, weight, (weight, heaviest_leaf))
				break
		if valid:
			yield (weight, heaviest_leaf)
			node = heaviest_leaf
			while node not in taken and node is not None:
				taken.add(node)
				node = path_from_root[node]

def get_next(tree, subtrees):
	heaviest_leaf_generators = [get_heaviest_leaves(tree, subtree) for subtree in subtrees]
	heaviest_leaves = []
	for gen in heaviest_leaf_generators:
		(weight, node) = next(gen)
		maxq.heappush(heaviest_leaves, weight, (weight, node, gen))
	while len(heaviest_leaves) > 0:
		(weight, heaviest_leaf, gen) = maxq.heappop(heaviest_leaves)
		yield weight
		next_heaviest_from_tree = next(gen, None)
		if next_heaviest_from_tree is not None:
			(weight, node) = next_heaviest_from_tree
			maxq.heappush(heaviest_leaves, weight, (weight, node, gen))

def get_diameter(tree):
	next_nodes = [next(iter(tree))]
	known = set(next_nodes)
	while len(next_nodes) > 0:
		current = next_nodes
		next_nodes = []
		for node in current:
			for next_node in tree[node]:
				if next_node not in known:
					known.add(next_node)
					next_nodes += [next_node]
	root = node
	known = set([root])
	next_nodes = [root]
	path_from_root = {root: root}
	while len(next_nodes) > 0:
		current = next_nodes
		next_nodes = []
		for node in current:
			for next_node in tree[node]:
				if next_node not in known:
					known.add(next_node)
					next_nodes += [next_node]
					path_from_root[next_node] = node
	end_node = node
	path = [end_node]
	while path_from_root[path[-1]] != path[-1]:
		path += [path_from_root[path[-1]]]
	return path

def solve(edges, k):
	if k == 1:
		return 1
	tree = {i: [] for edge in edges for i in edge}
	for edge in edges:
		tree[edge[0]] += [edge[1]]
		tree[edge[1]] += [edge[0]]
	diameter = get_diameter(tree)
	k -= len(diameter)
	subtrees_rooted_on_diameter = get_subtrees_rooted_on_path(tree, diameter)
	s = 2
	for weight in get_next(tree, subtrees_rooted_on_diameter):
		if k <= 0:
			break
		k -= weight
		s += 1
	return s
import sys
T = int(next(sys.stdin))
for _ in range(T):
	(n, k) = map(int, next(sys.stdin).split())
	edges = []
	for _ in range(n - 1):
		edge = tuple(map(int, next(sys.stdin).split()))
		edges += [edge]
	print(solve(edges, k))


from collections import deque

def bfs(tree, n):
	q = deque()
	visited = [0 for i in range(n + 1)]
	d = dict()
	for i in range(1, n + 1):
		if len(tree[i]) == 1:
			q.append(i)
			d[i] = 0
	res = []
	lv = 0
	while q:
		u = q.popleft()
		visited[u] += 1
		d[u] += 1
		lv = d[u]
		for v in tree[u]:
			if visited[v] == len(tree[v]):
				continue
			visited[v] += 1
			if v not in d:
				d[v] = d[u]
			else:
				l = min(d[v], d[u])
				d[v] = d[v] + d[u] - l
				res.append(l)
			if visited[v] == len(tree[v]) - 1:
				q.append(v)
	res.append(lv)
	res.sort(reverse=True)
	return res
for t in range(int(input())):
	(n, k) = tuple(map(int, input().strip().split()))
	tree = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = tuple(map(int, input().strip().split()))
		tree[u].append(v)
		tree[v].append(u)
	ans = k
	if k > 2:
		res = bfs(tree, n)
		n_r = len(res)
		ans = 2
		cnt = res[0] + res[1]
		i = 2
		while cnt < k and i < n_r:
			cnt += res[i]
			ans += 1
			i += 1
	print(ans)


from heapq import heapify, heappush, heappop
import sys
sys.setrecursionlimit(10 ** 6)

def mxbfs(u, g, n):
	s = [-1] * (n + 1)
	q = [u] * n
	s[u] = 0
	i = 0
	j = 1
	while i < n:
		u = q[i]
		i += 1
		for v in g[u]:
			if s[v] == -1:
				s[v] = s[u] + 1
				q[j] = v
				j += 1
	return s.index(max(s))

def maketree(u, g, r, d):
	d[u] = True
	m = 0
	for v in g[u]:
		if not d[v]:
			node = maketree(v, g, r, d)
			r[u].append(node)
			m = min(m, node[0])
	return [m - 1, u]
t = int(input())
z = [0] * t
for a in range(t):
	(n, k) = [int(i) for i in input().split()]
	g = {}
	vis = [False] * (n + 1)
	for i in range(1, n + 1):
		g[i] = []
	for j in range(n - 1):
		(u, v) = [int(i) for i in input().split()]
		g[u].append(v)
		g[v].append(u)
	if k == 1:
		z[a] = k
		continue
	ed = mxbfs(1, g, n)
	r = {}
	for i in range(1, n + 1):
		r[i] = []
	node = maketree(ed, g, r, vis)
	try:
		cover = 0
		forest = [node]
		ans = 1
		while cover < k:
			ans += 1
			node = heappop(forest)
			while node:
				cover += 1
				tree = r[node[1]]
				m = [0, 0]
				node = []
				for i in tree:
					if i[0] < m[0]:
						m = i
				for i in tree:
					if i[1] == m[1]:
						node = i
					else:
						heappush(forest, i)
		z[a] = ans
	except Exception:
		break
print(*z, sep='\n')


import sys
sys.setrecursionlimit(10 ** 9)

def fix(nod, par, gr, H):
	leafs = True
	for cnod in gr[nod]:
		if cnod == par:
			continue
		leafs = False
		fix(cnod, nod, gr, H)
		H[nod] = max(H[nod], 1 + H[cnod])
	if leafs:
		H[nod] = 1

def get(node, gr, n):
	sol = [False] * (n + 1)
	l = -1
	dr = None
	qu = [(node, 0)]
	sol[node] = True
	while qu:
		(nod, dis) = qu.pop(0)
		if l < dis:
			l = dis
			dr = nod
		for cnod in gr[nod]:
			if sol[cnod]:
				continue
			sol[cnod] = True
			qu.append((cnod, dis + 1))
	return dr

def dfs(nod, par, gr, H, li, cur):
	isleaf = True
	mx = 0
	for cnod in gr[nod]:
		if cnod == par:
			continue
		isleaf = False
		mx = max(mx, H[cnod])
	if isleaf:
		li.append(cur)
		return
	c = 0
	for cnod in gr[nod]:
		if cnod == par:
			continue
		if H[cnod] == mx and c == 0:
			dfs(cnod, nod, gr, H, li, cur + 1)
			c += 1
		else:
			dfs(cnod, nod, gr, H, li, 1)

def getinto(nod, par, gr, li, n, cur):
	H = [0] * (n + 1)
	fix(nod, par, gr, H)
	dfs(nod, par, gr, H, li, 1)

def sol(li, n, k):
	if k == 1:
		return 1
	u = get(1, li, n)
	lis = []
	siz = 1
	value = 0
	i = 0
	getinto(u, 0, li, lis, n, 1)
	lis.sort(reverse=True)
	while value < k:
		siz += 1
		value += lis[i]
		i += 1
	return siz
for i in range(int(input())):
	(n, k) = map(int, input().split())
	lis = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		lis[u].append(v)
		lis[v].append(u)
	c = sol(lis, n, k)
	print(c)


import sys
sys.setrecursionlimit(10 ** 9)

def avail_long(head, lists, n):
	dis = -1
	longs = None
	que = [(head, 0)]
	done = [False] * (n + 1)
	done[head] = True
	while que:
		(node, dist) = que.pop(0)
		if dis < dist:
			dis = dist
			longs = node
		for i in lists[node]:
			if done[i]:
				continue
			done[i] = True
			que.append((i, dist + 1))
	return longs

def avail(hd, val, lists, H):
	leaf = True
	for i in lists[hd]:
		if i == val:
			continue
		leaf = False
		avail(i, hd, lists, H)
		H[hd] = max(H[hd], 1 + H[i])
	if leaf:
		H[hd] = 1

def depth(hd, val, lists, H, li, cur):
	l = True
	maxi = 0
	for node in lists[hd]:
		if node == val:
			continue
		l = False
		maxi = max(maxi, H[node])
	if l:
		li.append(cur)
		return
	c = 0
	for node in lists[hd]:
		if node == val:
			continue
		if H[node] == maxi and c == 0:
			depth(node, hd, lists, H, li, cur + 1)
			c += 1
		else:
			depth(node, hd, lists, H, li, 1)

def divide(hd, val, lists, li, n, present):
	al = [0] * (n + 1)
	avail(hd, val, lists, al)
	depth(hd, val, lists, al, li, 1)

def func(lists, n, k):
	if k == 1:
		return 1
	u = avail_long(1, lists, n)
	arr = []
	var = 0
	divide(u, 0, lists, arr, n, 1)
	arr.sort(reverse=True)
	length = 1
	ans = 0
	while ans < k:
		ans += arr[var]
		length += 1
		var += 1
	return length
for test in range(int(input())):
	(n, k) = map(int, input().split())
	lists = [[] for i in range(n + 1)]
	for var in range(n - 1):
		(ord1, ord2) = map(int, input().split())
		lists[ord1].append(ord2)
		lists[ord2].append(ord1)
	sol = func(lists, n, k)
	print(sol)


import sys
sys.setrecursionlimit(10 ** 9)

def getFar(node, kl, n):
	done = [False] * (n + 1)
	nc = -1
	far = None
	qd = [(node, 0)]
	done[node] = True
	while qd:
		(nod, dis) = qd.pop(0)
		if nc < dis:
			nc = dis
			far = nod
		for cnod in kl[nod]:
			if done[cnod]:
				continue
			done[cnod] = True
			qd.append((cnod, dis + 1))
	return far

def fixHeight(nod, par, kl, H):
	isLeaf = True
	for cnod in kl[nod]:
		if cnod == par:
			continue
		isLeaf = False
		fixHeight(cnod, nod, kl, H)
		H[nod] = max(H[nod], 1 + H[cnod])
	if isLeaf:
		H[nod] = 1

def dfs(nod, par, kl, H, bi, cur):
	isLeaf = True
	ax = 0
	for cnod in kl[nod]:
		if cnod == par:
			continue
		isLeaf = False
		ax = max(ax, H[cnod])
	if isLeaf:
		bi.append(cur)
		return
	c = 0
	for cnod in kl[nod]:
		if cnod == par:
			continue
		if H[cnod] == ax and c == 0:
			dfs(cnod, nod, kl, H, bi, cur + 1)
			c += 1
		else:
			dfs(cnod, nod, kl, H, bi, 1)

def breakIntoLines(nod, par, kl, bi, n, cur):
	H = [0] * (n + 1)
	fixHeight(nod, par, kl, H)
	dfs(nod, par, kl, H, bi, 1)

def GETSOL(kl, n, k):
	if k == 1:
		return 1
	u = getFar(1, kl, n)
	bi = []
	breakIntoLines(u, 0, kl, bi, n, 1)
	bi.sort(reverse=True)
	size = 1
	tot = 0
	i = 0
	while tot < k:
		size += 1
		tot += bi[i]
		i += 1
	return size
for case in range(int(input())):
	(n, k) = map(int, input().split())
	kl = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		kl[u].append(v)
		kl[v].append(u)
	ans = GETSOL(kl, n, k)
	print(ans)


def get_diameter_node(edges, n):
	visited = [0] * n
	stack = [1]
	depth = {1: 1}
	deapest = 1
	while len(stack) > 0:
		cur = stack.pop()
		visited[cur - 1] = 1
		for neighbour in edges[cur]:
			if visited[neighbour - 1] == 0:
				stack.append(neighbour)
				depth[neighbour] = depth[cur] + 1
				if depth[neighbour] > depth[deapest]:
					deapest = neighbour
	return deapest

def get_contributions(edges, n, node):
	visited = [0] * n
	stack = [node]
	depth = {node: 1}
	contribution = {}
	contribution_list = []
	while len(stack) > 0:
		cur = stack[-1]
		if visited[cur - 1] == 0:
			visited[cur - 1] = 1
			for neighbour in edges[cur]:
				if visited[neighbour - 1] == 0:
					flag = False
					stack.append(neighbour)
					depth[neighbour] = depth[cur] + 1
		else:
			m = 0
			temp = []
			for neighbour in edges[cur]:
				if neighbour in contribution:
					m = max(m, contribution[neighbour])
					temp.append(contribution[neighbour])
			if m == 0:
				contribution[cur] = depth[cur]
			else:
				contribution[cur] = m
			flag = True
			for i in temp:
				if flag and i == m:
					flag = False
				else:
					contribution_list.append(i - depth[cur])
			stack.pop()
			if len(stack) == 0:
				contribution_list.append(contribution[cur])
	return sorted(contribution_list, reverse=True)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	edges = {}
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		if a not in edges:
			edges[a] = []
		if b not in edges:
			edges[b] = []
		edges[a].append(b)
		edges[b].append(a)
	if n == 1 or k == 1:
		print(1)
		continue
	node = get_diameter_node(edges, n)
	contri = get_contributions(edges, n, node)
	total = 0
	ans = 0
	for i in range(len(contri)):
		total += contri[i]
		if total >= k:
			ans = i + 2
			break
	print(ans)


import sys
sys.setrecursionlimit(10 ** 9)

def Far(node, grp, n):
	done = [False] * (n + 1)
	fd = -1
	far = None
	qu = [(node, 0)]
	done[node] = True
	while qu:
		(nod, dis) = qu.pop(0)
		if fd < dis:
			fd = dis
			far = nod
		for cnod in grp[nod]:
			if done[cnod]:
				continue
			done[cnod] = True
			qu.append((cnod, dis + 1))
	return far

def fixHeighT(nod, par, gr, H):
	isleaf = True
	for cnod in gr[nod]:
		if cnod == par:
			continue
		isleaf = False
		fixHeighT(cnod, nod, gr, H)
		H[nod] = max(H[nod], 1 + H[cnod])
	if isleaf:
		H[nod] = 1

def dfss(nod, par, gr, H, li, cur):
	isleaf = True
	mx = 0
	for cnod in gr[nod]:
		if cnod == par:
			continue
		isleaf = False
		mx = max(mx, H[cnod])
	if isleaf:
		li.append(cur)
		return
	c = 0
	for cnod in gr[nod]:
		if cnod == par:
			continue
		if H[cnod] == mx and c == 0:
			dfss(cnod, nod, gr, H, li, cur + 1)
			c += 1
		else:
			dfss(cnod, nod, gr, H, li, 1)

def breakIntoLines(nod, par, gr, li, n, cur):
	H = [0] * (n + 1)
	fixHeighT(nod, par, gr, H)
	dfss(nod, par, gr, H, li, 1)

def GETSolution(grp, n, k):
	if k == 1:
		return 1
	u = Far(1, grp, n)
	li = []
	breakIntoLines(u, 0, grp, li, n, 1)
	li.sort(reverse=True)
	size = 1
	total = 0
	i = 0
	while total < k:
		size += 1
		total += li[i]
		i += 1
	return size
for case in range(int(input())):
	(nn, kk) = map(int, input().split())
	grp = [[] for i in range(nn + 1)]
	for i in range(nn - 1):
		(u, v) = map(int, input().split())
		grp[u].append(v)
		grp[v].append(u)
	chad = GETSolution(grp, nn, kk)
	print(chad)


import sys
sys.setrecursionlimit(10 ** 9)

def getFar(node, gr, n):
	do = [False] * (n + 1)
	fd = -1
	f = None
	qu = [(node, 0)]
	do[node] = True
	while qu:
		(nod, dis) = qu.pop(0)
		if fd < dis:
			fd = dis
			f = nod
		for cnod in gr[nod]:
			if do[cnod]:
				continue
			do[cnod] = True
			qu.append((cnod, dis + 1))
	return f

def fixH(nod, par, gr, H):
	isleaf = True
	for cnod in gr[nod]:
		if cnod == par:
			continue
		isleaf = False
		fixH(cnod, nod, gr, H)
		H[nod] = max(H[nod], 1 + H[cnod])
	if isleaf:
		H[nod] = 1

def dfs(nod, par, gr, H, li, cur):
	isleaf = True
	mx = 0
	for cnod in gr[nod]:
		if cnod == par:
			continue
		isleaf = False
		mx = max(mx, H[cnod])
	if isleaf:
		li.append(cur)
		return
	c = 0
	for cnod in gr[nod]:
		if cnod == par:
			continue
		if H[cnod] == mx and c == 0:
			dfs(cnod, nod, gr, H, li, cur + 1)
			c += 1
		else:
			dfs(cnod, nod, gr, H, li, 1)

def breakIL(nod, par, gr, li, n, cur):
	H = [0] * (n + 1)
	fixH(nod, par, gr, H)
	dfs(nod, par, gr, H, li, 1)

def solve(gr, n, k):
	if k == 1:
		return 1
	u = getFar(1, gr, n)
	li = []
	breakIL(u, 0, gr, li, n, 1)
	li.sort(reverse=True)
	size = 1
	total = 0
	i = 0
	while total < k:
		size += 1
		total += li[i]
		i += 1
	return size
for case in range(int(input())):
	(n, k) = map(int, input().split())
	gr = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		gr[u].append(v)
		gr[v].append(u)
	ch = solve(gr, n, k)
	print(ch)