A tree is an undirected connected graph in which there are no cycles. This problem is about non-rooted trees. A leaf of a tree is a vertex that is connected to at most one vertex.

The gardener Vitaly grew a tree from $n$ vertices. He decided to trim the tree. To do this, he performs a number of operations. In one operation, he removes all leaves of the tree.

Example of a tree.

For example, consider the tree shown in the figure above. The figure below shows the result of applying exactly one operation to the tree.

The result of applying the operation "remove all leaves" to the tree.

Note the special cases of the operation:

applying an operation to an empty tree (of $0$ vertices) does not change it;

applying an operation to a tree of one vertex removes this vertex (this vertex is treated as a leaf);

applying an operation to a tree of two vertices removes both vertices (both vertices are treated as leaves).

Vitaly applied $k$ operations sequentially to the tree. How many vertices remain?


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case is preceded by an empty line.

Each test case consists of several lines. The first line of the test case contains two integers $n$ and $k$ ($1 \le n \le 4 \cdot 10^5$, $1 \le k \le 2 \cdot 10^5$) — the number of vertices in the tree and the number of operations, respectively. Then $n - 1$ lines follow, each of them contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$) which describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree and has no loops or multiple edges.

It is guaranteed that the sum of $n$ from all test cases does not exceed $4 \cdot 10^5$.


-----Output-----

For each test case output on a separate line a single integer — the number of vertices that remain in the tree after applying $k$ operations.


-----Examples-----

Input
6

14 1
1 2
2 3
2 4
4 5
4 6
2 7
7 8
8 9
8 10
3 11
3 12
1 13
13 14

2 200000
1 2

3 2
1 2
2 3

5 1
5 1
3 2
2 1
5 4

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

7 1
4 3
5 1
1 3
6 1
1 7
2 1
Output
7
0
0
3
1
2


-----Note-----

The first test case is considered in the statement.

The second test case contains a tree of two vertices. $200000$ operations are applied to it. The first one removes all two vertices, the other operations do not change the tree.

In the third test case, a tree of three vertices is given. As a result of the first operation, only $1$ vertex remains in it (with the index $2$), the second operation makes the tree empty.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph traversal

Implementation

Complete search

Greedy algorithms

Tree algorithms

Data structures


Solutions:
import sys
input = sys.stdin.readline
from collections import deque

def solve(n, k, adj):
	ver = n
	indeg = [len(adj[z]) for z in range(n + 1)]
	bfs = deque()
	for i in range(1, n + 1):
		if indeg[i] == 1:
			bfs.append(i)
	bfs.append(-1)
	while k:
		if ver < 3:
			return 0
		ver -= len(bfs) - 1
		while bfs[0] != -1:
			node = bfs.popleft()
			for each in adj[node]:
				indeg[each] -= 1
				if indeg[each] == 1:
					bfs.append(each)
		bfs.popleft()
		bfs.append(-1)
		k -= 1
	return ver
t = int(input())
for _ in range(t):
	emp = input()
	(n, k) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	print(solve(n, k, adj))


import sys
input = sys.stdin.readline

def solve():
	input()
	(N, K) = map(int, input().split())
	if N == 1:
		print(0)
		return
	G = [set() for _ in range(N)]
	for _ in range(N - 1):
		(u, v) = map(int, input().split())
		G[u - 1].add(v - 1)
		G[v - 1].add(u - 1)
	ans = N
	rm = set((u for u in range(N) if len(G[u]) == 1))
	for _ in range(K):
		if not rm:
			break
		ans -= len(rm)
		rm2 = set()
		for u in rm:
			if len(G[u]) == 0:
				continue
			v = next(iter(G[u]))
			G[v].remove(u)
			if len(G[v]) == 1:
				rm2.add(v)
		rm = rm2 - rm
	print(ans)
for _ in range(int(input())):
	solve()


from collections import deque, defaultdict

def ans(n, k):
	graph = defaultdict(list)
	incoming = [0] * (n + 1)
	for _ in range(n - 1):
		(t1, t2) = map(int, input().split())
		graph[t1].append(t2)
		graph[t2].append(t1)
		incoming[t1] += 1
		incoming[t2] += 1
	if n < 3:
		return 0
	pq = deque()
	visited = set()
	for node in graph:
		if incoming[node] == 1:
			pq.append(node)
			visited.add(node)
	while pq and k > 1:
		for _ in range(len(pq)):
			cur = pq.popleft()
			for negbour in graph[cur]:
				if negbour in visited:
					continue
				incoming[negbour] -= 1
				if incoming[negbour] == 1:
					pq.append(negbour)
					visited.add(negbour)
		k -= 1
	return n - len(visited)
for _ in range(int(input())):
	_ = input()
	(n, k) = map(int, input().split())
	print(ans(n, k))


import sys
N = int(1000000.0 + 5)
sys.setrecursionlimit(N)
(n, k) = (int(), int())
adj = list()

def charming():
	global n, k, adj
	input()
	(n, k) = map(int, input().split())
	adj = list((list() for i in range(n + 1)))
	vis = set()
	du = [0] * (n + 1)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
		du[u] += 1
		du[v] += 1
	leaf = list()
	for i in range(1, n + 1):
		if du[i] <= 1:
			leaf.append(i)
			vis.add(i)
	nleaf = list()
	for i in range(k - 1):
		nleaf = list()
		for u in leaf:
			for v in adj[u]:
				if v in vis:
					continue
				du[v] -= 1
				if du[v] <= 1:
					vis.add(v)
					nleaf.append(v)
		leaf = nleaf
		if len(leaf) <= 0:
			break
	print(n - len(vis))
for t in range(int(input())):
	charming()


def f():
	input()
	(n, k) = map(int, input().split())
	if n == 1:
		print(0 if k else 1)
		return
	g = [set() for i in range(n)]
	q = set()
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		g[a].add(b)
		g[b].add(a)
	for i in range(n):
		if len(g[i]) == 1:
			q.add(i)
	ans = set()
	while k and q:
		k -= 1
		p = set()
		for i in q:
			ans.add(i)
			if len(g[i]) == 0:
				continue
			t = list(g[i])[0]
			g[t].discard(i)
			if len(g[t]) == 1:
				p.add(t)
		q = p - q
	print(n - len(ans))
for _ in range(int(input())):
	f()


import sys
from collections import deque
read = sys.stdin.readline
for _ in range(int(read())):
	read()
	(n, k) = map(int, read().split())
	data = [[] for _ in range(n + 1)]
	in_degree = [0] * (n + 1)
	for _ in range(n - 1):
		(v, w) = map(int, read().split())
		data[v].append(w)
		data[w].append(v)
		in_degree[v] += 1
		in_degree[w] += 1
	q = deque()
	size = 0
	for v in range(1, n + 1):
		if in_degree[v] == 1:
			q.append(v)
			size += 1
	deleted = [0] * (n + 1)
	num = n
	for _ in range(k):
		if num == 1 or num == 2 or num == 0:
			num = 0
			break
		new_size = 0
		for _ in range(size):
			v = q.popleft()
			deleted[v] = 1
			num -= 1
			for w in data[v]:
				if not deleted[w]:
					in_degree[w] -= 1
					if in_degree[w] == 1:
						q.append(w)
						new_size += 1
		size = new_size
	print(num)


import sys
input = sys.stdin.readline

def solution(edges: list, n, k):
	if k > n / 2:
		return 0
	adj_list = [set() for _ in range(n)]
	for (u, v) in edges:
		adj_list[u].add(v)
		adj_list[v].add(u)
	n_removed = 0
	degree = [len(adj_list[v]) for v in range(n)]
	leaves = [v for v in range(n) if degree[v] == 1]
	for _ in range(k):
		if n_removed == n - 1:
			return 0
		neighbors = set()
		for leaf in leaves:
			neighbors.update(adj_list[leaf])
			degree[leaf] = 0
			n_removed += 1
			for neighbor in adj_list[leaf]:
				degree[neighbor] -= 1
		leaves = [v for v in neighbors if degree[v] == 1]
	return n - n_removed

def main():
	for _ in range(int(input())):
		input()
		(n, k) = map(int, input().split())
		edges = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n - 1)]
		print(solution(edges, n, k))

def test():
	edges = [(1, 0), (2, 1)]
	print(solution(edges, 3, 2))
main()


T = int(input())
for t in range(T):
	input()
	(V, K) = map(int, input().split())
	adj = [set() for i in range(V)]
	for i in range(V - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].add(v - 1)
		adj[v - 1].add(u - 1)
	leaves = []
	for i in range(V):
		if len(adj[i]) == 1:
			leaves.append(i)
	rem = V
	while rem > 2 and K > 0:
		K -= 1
		rem -= len(leaves)
		temp = []
		while leaves:
			leaf = leaves.pop()
			succ = adj[leaf].pop()
			adj[succ].remove(leaf)
			if len(adj[succ]) == 1:
				temp.append(succ)
		leaves = temp
	if K == 0:
		print(rem)
	else:
		print(0)


for _ in range(int(input())):
	input()
	(n, k) = map(int, input().split())
	graph = [[] for _ in range(n + 1)]
	remain = [0] * (n + 1)
	layer = [0] * (n + 1)
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
		remain[u] += 1
		remain[v] += 1
	leaves = []
	for i in range(1, n + 1):
		if remain[i] == 1:
			leaves.append(i)
			layer[i] = 1
	for i in leaves:
		for j in graph[i]:
			if remain[j] != 1:
				remain[j] -= 1
				if remain[j] == 1:
					layer[j] = layer[i] + 1
					leaves.append(j)
	ans = 0
	for i in range(1, n + 1):
		if layer[i] > k:
			ans += 1
	print(ans)


def remove_leaves(graph, leaves, removed_leaves, removed_neighbours_count, beginning_neighbours_count):
	removed_leaves.update(leaves)
	new_leaves = set()
	for leave in leaves:
		for neighbour in graph[leave]:
			if neighbour not in removed_leaves:
				removed_neighbours_count[neighbour] += 1
				if removed_neighbours_count[neighbour] >= beginning_neighbours_count[neighbour] - 1:
					new_leaves.add(neighbour)
	return list(new_leaves)
tests = int(input())
for i in range(tests):
	empty_line = input()
	[vertex_count, operations] = [int(el) for el in input().split()]
	graph = [[] for t in range(vertex_count)]
	for j in range(vertex_count - 1):
		[u, w] = [int(el) for el in input().split()]
		graph[u - 1].append(w - 1)
		graph[w - 1].append(u - 1)
	visited = [False] * vertex_count
	leaves = [idx for (idx, el) in enumerate(graph) if len(el) in [0, 1]]
	beginning_neighbours_count = [len(el) for el in graph]
	removed_neighbours_count = [0] * vertex_count
	removed_leaves = set()
	for _ in range(operations):
		leaves = remove_leaves(graph, leaves, removed_leaves, removed_neighbours_count, beginning_neighbours_count)
		if len(graph) == len(removed_leaves):
			break
	print(len(graph) - len(removed_leaves))


from collections import deque
for _ in range(int(input())):
	input()
	(n, k) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	depth = [0]
	for i in range(1, n + 1):
		depth.append(len(adj[i]))
	tree = [0]
	for i in range(1, n + 1):
		tree.append(1) if depth[i] == 1 else tree.append(-1)
	arr = [i for i in range(n + 1) if tree[i] == 1]
	queue = deque(arr)
	while queue:
		node = queue.popleft()
		for i in adj[node]:
			depth[i] -= 1
			if depth[i] == 1:
				tree[i] = tree[node] + 1
				queue.append(i)
	cnt = -1
	for v in tree:
		if v <= k:
			cnt += 1
	print(n - cnt)


import math
import heapq
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
H = 1000000000 + 7
for _ in range(I()):
	s = S()
	(n, k) = M()
	adj = [[] for i in range(n)]
	d = [0] * n
	for i in range(n - 1):
		(a, b) = M()
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
		d[a - 1] += 1
		d[b - 1] += 1
	ans = n
	q = deque()
	for i in range(n):
		if d[i] == 1:
			q.append(i)
	for p in range(k):
		if len(q) == 0 or ans == 1:
			ans = 0
			break
		for i in range(len(q)):
			t = q.popleft()
			d[t] = 0
			ans -= 1
			for j in adj[t]:
				d[j] -= 1
				if d[j] == 1:
					q.append(j)
	print(ans)


def gardener_and_tree(edges, n, k):
	next_step = []
	for vertex in edges:
		if len(edges[vertex]) <= 1:
			next_step += [vertex]
	for j in range(k):
		to_remove = next_step
		if len(to_remove) == 0:
			return 0
		next_step = []
		for vertex_to_remove in to_remove:
			try:
				connected = edges[vertex_to_remove].pop()
				edges[connected].remove(vertex_to_remove)
				if len(edges[connected]) == 1:
					next_step += [connected]
			except KeyError:
				pass
			del edges[vertex_to_remove]
	count = len(edges.keys())
	return count
t = int(input())
for _ in range(t):
	input()
	(n, k) = map(int, input().split())
	edges = {}
	for _ in range(n - 1):
		(a, b) = map(int, input().split(' '))
		if a in edges:
			edges[a].add(b)
		else:
			edges[a] = {b}
		if b in edges:
			edges[b].add(a)
		else:
			edges[b] = {a}
	print(gardener_and_tree(edges, n, k))


from collections import deque
for _ in range(int(input())):
	input()
	(n, k) = map(int, input().split())
	adj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	layer = [-1 for _ in range(n)]
	rem = [len(adj[i]) for i in range(n)]
	q = deque()
	for node in range(n):
		if len(adj[node]) <= 1:
			q.append(node)
			layer[node] = 1
	while q:
		current = q.popleft()
		for nei in adj[current]:
			if rem[nei] != 1:
				rem[nei] -= 1
				if rem[nei] == 1:
					q.append(nei)
					layer[nei] = layer[current] + 1
	count = 0
	for i in range(n):
		if layer[i] > k:
			count += 1
	print(count)


for _ in range(int(input())):
	__ = input()
	(n, k) = map(int, input().split())
	tt = k
	d = {i: [] for i in range(n)}
	ideg = [0 for _ in range(n)]
	v = [0 for _ in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		d[a - 1].append(b - 1)
		d[b - 1].append(a - 1)
		ideg[b - 1] += 1
		ideg[a - 1] += 1
	q = []
	if k:
		for i in range(n):
			if ideg[i] == 1:
				q.append(i)
				v[i] = 1
	k -= 1
	while q and k:
		q1 = []
		for node in q:
			for child in d[node]:
				if v[child] == 0:
					ideg[child] -= 1
					if ideg[child] == 1:
						v[child] = 1
						q1.append(child)
		q = q1
		k -= 1
	if n == 1:
		if tt:
			print(0)
		else:
			print(1)
	else:
		print(v.count(0))


from sys import stdin
from collections import deque
input = stdin.readline
test = int(input())
for _ in range(test):
	_ = input()
	(n, k) = map(int, input().split())
	edges = {i: [] for i in range(1, n + 1)}
	degree = {i: 0 for i in range(1, n + 1)}
	queue = deque()
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		edges[a].append(b)
		edges[b].append(a)
		degree[a] += 1
		degree[b] += 1
	(remove, total, step, current) = (set(), 0, 0, 0)
	for i in range(1, n + 1):
		if degree[i] <= 1:
			remove.add(i)
			degree.pop(i)
			current += 1
	k -= 1
	while degree and step < k:
		newremove = set()
		for r in remove:
			for edge in edges[r]:
				if edge in degree and edge not in remove:
					degree[edge] -= 1
					if degree[edge] <= 1:
						degree.pop(edge)
						newremove.add(edge)
		(remove, step) = (newremove.copy(), step + 1)
	print(len(degree))


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	sys.stderr = open('error.txt', 'w')
depth = 1000000
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
linp = lambda : list(minp())
minp = lambda : map(int, input().split())
from math import inf, ceil, sqrt, log2, gcd
from collections import defaultdict, deque
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for _ in range(int(input())):
	input()
	(n, k) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	deg = [0 for _ in range(n + 1)]
	lay = [0 for _ in range(n + 1)]
	for _ in range(1, n):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
		deg[u] += 1
		deg[v] += 1
	q = deque()
	for i in range(1, n + 1):
		if deg[i] == 1:
			lay[i] = 1
			q.append(i)
	while q:
		u = q.popleft()
		for v in adj[u]:
			deg[v] -= 1
			if deg[v] == 1:
				lay[v] = lay[u] + 1
				q.append(v)
	ans = 0
	for i in range(1, n + 1):
		if lay[i] > k:
			ans += 1
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	aaa = input()
	(n, k) = map(int, input().split())
	d = defaultdict(list)
	deg = [0] * (n + 1)
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		d[x].append(y)
		d[y].append(x)
		deg[x] += 1
		deg[y] += 1
	leaf = []
	for i in range(1, 1 + n):
		if deg[i] == 1:
			leaf.append(i)
	ans = n
	while len(leaf) and k:
		ans -= len(leaf)
		k -= 1
		st = []
		for i in leaf:
			for j in d[i]:
				deg[j] -= 1
				if deg[j] == 1:
					st.append(j)
		leaf = st
	if n == 1:
		print(0)
	else:
		print(ans)


from collections import defaultdict, deque
from sys import stdin, stdout
t = int(stdin.readline().strip())
for _ in range(t):
	stdin.readline().strip()
	(n, k) = map(int, stdin.readline().split())
	graph = defaultdict(list)
	in_degree = defaultdict(int)
	for _ in range(n - 1):
		(u, v) = map(int, stdin.readline().split())
		graph[u].append(v)
		graph[v].append(u)
		in_degree[u] += 1
		in_degree[v] += 1
	starting_nodes = list(map(lambda x: (x, 0), filter(lambda x: in_degree[x] <= 1, range(1, n + 1))))
	deleted = 0
	starting_nodes = deque(starting_nodes)
	while starting_nodes:
		(node, depth) = starting_nodes.popleft()
		deleted += 1
		for nei in graph[node]:
			in_degree[nei] -= 1
			if in_degree[nei] == 1 and depth + 1 < k:
				starting_nodes.append((nei, depth + 1))
	print(n - deleted)


from collections import defaultdict, deque
for t in range(int(input())):
	input()
	(n, k) = map(int, input().split())
	graph = defaultdict(list)
	visited = set()
	degree = [0] * n
	for _ in range(n - 1):
		(s, e) = map(int, input().split())
		degree[s - 1] += 1
		graph[e].append(s)
		degree[e - 1] += 1
		graph[s].append(e)
	if k >= n:
		print(0)
		continue
	todo = deque([])
	for (index, count) in enumerate(degree):
		if count == 1:
			todo.append(index + 1)
			degree[index] -= 1
	while todo and k:
		for _ in range(len(todo)):
			node = todo.popleft()
			n -= 1
			for neighbour in graph[node]:
				degree[neighbour - 1] -= 1
				if degree[neighbour - 1] == 1:
					todo.append(neighbour)
		k -= 1
	print(n)


from collections import deque
t = int(input())
for _ in range(t):
	input()
	(n, k) = map(int, input().split())
	v = [[] for _ in range(n + 1)]
	d = [0 for _ in range(n + 1)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		v[a].append(b)
		v[b].append(a)
		d[a] += 1
		d[b] += 1
	q = deque()
	for i in range(1, n + 1):
		if d[i] < 2:
			q.append(i)
	did = [0 for _ in range(n + 1)]
	res = n
	for _ in range(k):
		p = deque()
		if len(q) == 0:
			break
		while len(q):
			x = q.popleft()
			if did[x] > 0:
				continue
			did[x] = 1
			res -= 1
			for i in v[x]:
				d[i] -= 1
				if d[i] == 1:
					p.append(i)
		q = p
	print(res)


import sys, heapq
from collections import defaultdict, deque
import math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
test = inp()
for k in range(test):
	input()
	(n, k) = invr()
	edges = defaultdict(list)
	indegree = [0] * (n + 1)
	for e in range(n - 1):
		(u, v) = invr()
		edges[u].append(v)
		indegree[u] += 1
		edges[v].append(u)
		indegree[v] += 1
	q = deque()
	for i in range(1, n + 1):
		if indegree[i] <= 1:
			q.append(i)
	count = 0
	removed = set()
	while q:
		if k:
			length = len(q)
			while length:
				node = q.popleft()
				if node not in removed:
					count += 1
					removed.add(node)
					for neigh in edges[node]:
						indegree[neigh] -= 1
						if indegree[neigh] <= 1:
							q.append(neigh)
				length -= 1
			k -= 1
		else:
			q = None
	print(n - count)


from collections import defaultdict

def read_nums():
	return [int(x) for x in input().split()]

def solve():
	(n, k) = read_nums()
	graph = defaultdict(set)
	for _ in range(n - 1):
		(u, v) = read_nums()
		graph[u].add(v)
		graph[v].add(u)
	leaves = {node for (node, neighbors) in graph.items() if len(neighbors) == 1}
	for _ in range(k):
		if len(graph) <= 2:
			print(0)
			return
		new_leaf_candidates = set()
		for leaf in leaves:
			(parent,) = graph[leaf]
			graph[parent].remove(leaf)
			del graph[leaf]
			new_leaf_candidates.add(parent)
		leaves = {p for p in new_leaf_candidates if len(graph[p]) == 1}
	print(len(graph))

def main():
	(t,) = read_nums()
	for _ in range(t):
		input()
		solve()
main()


from collections import defaultdict, deque
test = int(input())
for _ in range(test):
	val = input()
	graph = defaultdict(list)
	(n, k) = [int(x) for x in input().split()]
	if n == 1:
		graph[1].append(1)
		graph[1].pop()
	for _ in range(n - 1):
		(x, y) = [int(x) for x in input().split()]
		graph[x].append(y)
		graph[y].append(x)
	leaves = deque([])
	neigbour = defaultdict(int)
	for i in graph:
		if len(graph[i]) == 1 or len(graph[i]) == 0:
			leaves.append(i)
		else:
			neigbour[i] += len(graph[i])
	ans = 0
	while leaves and k:
		for _ in range(len(leaves)):
			new = leaves.popleft()
			ans += 1
			for val in graph[new]:
				neigbour[val] -= 1
				if neigbour[val] == 1:
					leaves.append(val)
		k -= 1
	print(n - ans)


from math import gcd
from collections import defaultdict
from collections import deque

def main():
	t = int(input())
	for _ in range(t):
		input()
		(n, k) = map(int, input().split())
		d = defaultdict(list)
		l = defaultdict(int)
		if n == 1:
			print(0)
			continue
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			d[u].append(v)
			d[v].append(u)
			l[u] += 1
			l[v] += 1
		q = deque()
		visited = set()
		cnt = 0
		for i in range(1, n + 1):
			if len(d[i]) == 1:
				q.append((i, k))
				visited.add(i)
		while len(q) != 0:
			(v, curr_k) = q.popleft()
			if curr_k == 0:
				break
			cnt += 1
			for e in d[v]:
				if e not in visited:
					if l[e] == 2:
						q.append((e, curr_k - 1))
						visited.add(e)
					else:
						l[e] -= 1
		print(n - cnt)
main()


from collections import defaultdict
from collections import deque
tc = int(input())
for _ in range(tc):
	input()
	graph = defaultdict(list)
	indegree = defaultdict(int)
	(n, k) = map(int, input().split())
	for _ in range(n - 1):
		(n1, n2) = map(int, input().split())
		graph[n1].append(n2)
		graph[n2].append(n1)
		indegree[n1] += 1
		indegree[n2] += 1
	q = deque()
	for (key, v) in indegree.items():
		if v == 1:
			q.append(key)
	count = 0
	while k > 0 and q:
		size = len(q)
		for _ in range(size):
			cur = q.popleft()
			count += 1
			for ne in graph[cur]:
				indegree[ne] -= 1
				if indegree[ne] == 1:
					q.append(ne)
		k -= 1
	if n <= 2:
		print(0)
	else:
		print(n - count)


from collections import defaultdict, deque

def solve():
	input()
	(n, k) = list(map(int, input().split()))
	edges = [list(map(int, input().split())) for _ in range(n - 1)]
	graph = defaultdict(list)
	for (a, b) in edges:
		graph[a].append(b)
		graph[b].append(a)
	indegrees = defaultdict(int)
	for (node, neighbours) in graph.items():
		for neighbour in neighbours:
			indegrees[neighbour] += 1
	with_1 = deque([])
	for x in range(1, n + 1):
		if indegrees[x] <= 1:
			with_1.append(x)
	pro = 0
	for x in range(k):
		if not with_1:
			break
		nex = deque([])
		while with_1:
			node = with_1.popleft()
			pro += 1
			for neighbor in graph[node]:
				indegrees[neighbor] -= 1
				if indegrees[neighbor] == 1:
					nex.append(neighbor)
		with_1 = nex
	print(n - pro)
for i in range(int(input())):
	solve()


import sys
import math

def readln_str():
	return input().split(' ')

def readln_int():
	return [int(i) for i in readln_str()]
T = eval(input())
for _ in range(T):
	input()
	(N, K) = readln_int()
	edges = [set() for _ in range(N)]
	deleted = [False] * N
	for _ in range(N - 1):
		(u, v) = readln_int()
		(u, v) = (u - 1, v - 1)
		edges[u].add(v)
		edges[v].add(u)
	(head, tail) = (0, 0)
	queue = set()
	for i in range(N):
		if len(edges[i]) <= 1:
			queue.add(i)
	for _ in range(K):
		if len(queue) == 0:
			break
		new_queue = set()
		for u in queue:
			deleted[u] = True
			for v in edges[u]:
				edges[v].discard(u)
				if not deleted[v] and len(edges[v]) <= 1:
					new_queue.add(v)
		queue = new_queue
	ans = sum((1 for u in range(N) if not deleted[u]))
	print(ans)


from collections import defaultdict, deque
for _ in range(int(input())):
	input()
	(n, k) = map(int, input().split())
	if n == 1:
		print(0)
		continue
	p = defaultdict(int)
	graph = defaultdict(list)
	for i in range(n - 1):
		(s, d) = map(int, input().split())
		graph[s].append(d)
		graph[d].append(s)
		p[d] += 1
		p[s] += 1
	q = deque()
	seen = set()
	for node in range(1, n + 1):
		if len(graph[node]) <= 1:
			q.append(node)
			seen.add(node)
	total = n
	for op in range(k):
		total -= len(q)
		temp = deque()
		for el in q:
			for src in graph[el]:
				if src not in seen:
					p[src] -= 1
					if p[src] == 1:
						temp.append(src)
						seen.add(src)
		q = temp
		if not q:
			break
	print(total)


from collections import defaultdict
from collections import deque
t = int(input())
for i in range(t):
	line = input()
	n_k = list(map(int, input().split()))
	(n, k) = (n_k[0], n_k[1])
	adjList = {}
	for m in range(1, n + 1):
		adjList[m] = []
	for j in range(n - 1):
		a_b = list(map(int, input().split()))
		adjList[a_b[0]].append(a_b[1])
		adjList[a_b[1]].append(a_b[0])
	queue = deque([])
	edgeCount = {}
	for node in adjList:
		edgeCount[node] = len(adjList[node])
		if edgeCount[node] == 1 or edgeCount[node] == 0:
			queue.append(node)
	totalRemoved = 0
	while queue and k > 0:
		curLevel = len(queue)
		totalRemoved += curLevel
		while curLevel > 0:
			curNode = queue.popleft()
			edgeCount[curNode] -= 1
			for nibr in adjList[curNode]:
				edgeCount[nibr] -= 1
				if edgeCount[nibr] == 1:
					queue.append(nibr)
			curLevel -= 1
		k -= 1
	print(n - totalRemoved)


from queue import deque
t = int(input())
for _ in range(t):
	input()
	(n, k) = map(int, input().split())
	edge_count = [0] * (n + 1)
	graph = {}
	for _1 in range(n - 1):
		(u, v) = map(int, input().split())
		if v not in graph:
			graph[v] = []
		if u not in graph:
			graph[u] = []
		graph[u].append(v)
		graph[v].append(u)
		edge_count[u] += 1
		edge_count[v] += 1
	q = deque()
	visited = set()
	for i in range(1, n + 1):
		if len(graph.get(i, [])) < 2:
			visited.add(i)
			q.append(i)
	nodes_left = n
	for i in range(k):
		if nodes_left <= 0:
			break
		l = len(q)
		for ij in range(l):
			v = q.popleft()
			for ngh in graph.get(v, []):
				edge_count[ngh] -= 1
				if edge_count[ngh] < 2 and ngh not in visited:
					visited.add(ngh)
					q.append(ngh)
		nodes_left -= l
	print(nodes_left)


t = int(input())
for _ in range(t):
	empty = input()
	(ni, k) = map(int, input().split())
	neighbors = {i: [] for i in range(ni)}
	for i in range(ni - 1):
		(v, w) = map(int, input().split())
		neighbors[v - 1].append(w - 1)
		neighbors[w - 1].append(v - 1)
	time = {}
	layer = []
	for i in range(ni):
		if len(neighbors[i]) <= 1:
			time[i] = 1
			layer.append(i)
	dist = 2
	while len(time) < ni and dist <= k:
		newlayer = set()
		for v in layer:
			for n in neighbors[v]:
				if n not in newlayer and n not in time:
					alive = 0
					for nn in neighbors[n]:
						if nn not in time or time[nn] == dist:
							alive += 1
							if alive == 2:
								break
					if alive < 2:
						newlayer.add(n)
						time[n] = dist
		dist += 1
		layer = newlayer
	print(ni - len(time))


from collections import deque
t = int(input())
for tt in range(t):
	input()
	(n, k) = map(int, input().split())
	tree = [set() for x in range(n + 1)]
	levels = [0 for x in range(n + 1)]
	visited = [False for x in range(n + 1)]
	lens = levels.copy()
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		tree[a].add(b)
		tree[b].add(a)
		lens[a] += 1
		lens[b] += 1
	q = deque()
	for (idx, v) in enumerate(tree):
		if len(v) <= 1:
			q.append(idx)
			levels[idx] = 1
			visited[idx] = True
	while len(q) > 0:
		node = q.popleft()
		if lens[node] == 0:
			continue
		v = tree[node].pop()
		tree[node].clear()
		lens[node] = 0
		tree[v].remove(node)
		lens[v] -= 1
		if levels[node] + 1 <= k and lens[v] == 1 and (not visited[v]):
			visited[v] = True
			levels[v] = levels[node] + 1
			q.append(v)
	print(sum([1 for (idx, level) in enumerate(levels) if idx != 0 and (level > k or level == 0)]))


from collections import deque

def getLeaves(g):
	res = []
	for i in g.keys():
		if len(g[i]) < 2:
			res.append(i)
	return res
n1 = int(input())
for i in range(n1):
	input()
	(n, k) = [int(k) for k in input().split()]
	g = {}
	for j in range(n - 1):
		(n1, n2) = [int(k) for k in input().split()]
		if n1 not in g.keys():
			g[n1] = []
		if n2 not in g.keys():
			g[n2] = []
		g[n1].append(n2)
		g[n2].append(n1)
	leaves = getLeaves(g)
	q = deque()
	layer = {}
	rem = {}
	for node in g.keys():
		rem[node] = len(g[node])
		layer[node] = 1
	for leave in leaves:
		q.append(leave)
	while q:
		node = q.popleft()
		for nei in g[node]:
			if rem[nei] > 1:
				layer[nei] = layer[node] + 1
				rem[nei] -= 1
				if rem[nei] == 1:
					q.append(nei)
	c = 0
	for val in layer.values():
		if val > k:
			c += 1
	print(c)


from collections import deque
t = int(input())
for c in range(t):
	input()
	(n, k) = [int(x) for x in input().split(' ')]
	adj = [set() for x in range(n)]
	conn = [0 for x in range(n)]
	dist = [1 for x in range(n)]
	visited = [False for x in range(n)]
	for i in range(n - 1):
		(u, v) = [int(x) - 1 for x in input().split(' ')]
		adj[u].add(v)
		adj[v].add(u)
		conn[u] += 1
		conn[v] += 1
	pending = deque()
	for (idx, val) in enumerate(conn):
		if val == 1:
			pending.append(idx)
			visited[idx] = True
	while len(pending):
		current = pending.popleft()
		for v in adj[current]:
			if not visited[v]:
				dist[v] = dist[current] + 1 if dist[current] + 1 > dist[v] else dist[v]
				conn[v] -= 1
				if conn[v] == 1:
					pending.append(v)
					visited[v] = True
	print(f'{len([x for x in dist if x > k])}')


from collections import defaultdict, deque

class Solution:

	def trimTree(self, n, k, edges):
		graph = defaultdict(list)
		if not edges:
			return 0
		indegree = {i: 0 for i in range(1, n + 1)}
		for (node1, node2) in edges:
			graph[node1].append(node2)
			graph[node2].append(node1)
			indegree[node1] += 1
			indegree[node2] += 1
		queue = deque()
		for node in graph:
			if indegree[node] == 1:
				queue.append(node)
		while queue and k > 0:
			size = len(queue)
			k -= 1
			for i in range(size):
				node = queue.popleft()
				n -= 1
				for neigh in graph[node]:
					indegree[neigh] -= 1
					if indegree[neigh] == 1:
						queue.append(neigh)
		return n
sol = Solution()
t = int(input())
inputs = []
for _ in range(t):
	input()
	(n, k) = list(map(int, input().split()))
	edges = []
	for i in range(n - 1):
		edges.append(list(map(int, input().split())))
	inputs.append([n, k, edges])
for (n, k, edges) in inputs:
	print(sol.trimTree(n, k, edges))


from collections import defaultdict, deque
from email.policy import default
t = int(input())
for tt in range(t):
	just = input()
	(n, ope) = list(map(int, input().split(' ')))
	graph = defaultdict(list)
	inDegree = defaultdict(int)
	for _ in range(n - 1):
		(first, second) = list(map(int, input().split(' ')))
		graph[first].append(second)
		graph[second].append(first)
		inDegree[first] += 1
		inDegree[second] += 1
	if n == 1:
		print(0)
	else:
		count = 0
		queue = deque()
		for i in range(1, n + 1):
			if inDegree[i] == 1:
				queue.append((i, 1))
		level = 1
		while queue:
			(cur, cur_level) = queue.popleft()
			if cur_level - 1 >= ope:
				break
			count += 1
			for neighbour in graph[cur]:
				inDegree[neighbour] -= 1
				if inDegree[neighbour] == 1:
					queue.append((neighbour, cur_level + 1))
		if cur_level - 1 < ope:
			print(0)
		else:
			print(n - count)


from collections import defaultdict, deque
t = int(input())
op = defaultdict(int)
for z in range(t):
	indgree = defaultdict(int)
	input()
	graph = defaultdict(list)
	(n, k) = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	for i in range(n - 1):
		(u, v) = list(map(int, input().split()))
		indgree[u] += 1
		indgree[v] += 1
		graph[u].append(v)
		graph[v].append(u)
	queue = deque()
	indCount = defaultdict(int)
	visited = set()
	for (node, ct) in indgree.items():
		if ct == 1:
			queue.append(node)
			visited.add(node)
	level = 0
	ct = 0
	while queue and level != k:
		for i in range(len(queue)):
			node = queue.popleft()
			if indgree[node] == 1:
				n -= 1
			for nxt in graph[node]:
				if nxt not in visited:
					indgree[nxt] -= 1
					if indgree[nxt] <= 1:
						queue.append(nxt)
						visited.add(nxt)
		level += 1
	print(n)


import sys
from collections import deque
for _ in range(int(input())):
	sys.stdin.readline()
	(n, k) = map(int, input().split())
	graph = {}
	for _ in range(n - 1):
		(x, y) = map(int, input().split())
		(x, y) = (x - 1, y - 1)
		if x in graph:
			graph[x].add(y)
		else:
			graph[x] = {y}
		if y in graph:
			graph[y].add(x)
		else:
			graph[y] = {x}
	level = [0] * n
	for i in graph:
		for j in graph[i]:
			level[j] += 1
	queue = deque([])
	visited = [False] * n
	s = [0] * n
	for i in range(n):
		if level[i] in [0, 1]:
			queue.append(i)
			visited[i] = True
			s[i] = 1
			level[i] -= 1
	while len(queue) != 0:
		x = queue.popleft()
		if x in graph:
			for i in graph[x]:
				level[i] -= 1
				if not visited[i] and level[i] in [0, 1]:
					visited[i] = True
					s[i] = s[x] + 1
					queue.append(i)
	ans = 0
	for i in s:
		if i > k:
			ans += 1
	print(ans)


import sys
from math import factorial, gcd
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest, nsmallest
from itertools import groupby, accumulate
from copy import deepcopy
MOD = 10 ** 9 + 7
INF = float('inf')
input = sys.stdin.readline
rl = lambda : list(map(int, input().split()))
rs = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	input()
	(n, k) = rl()
	graph = defaultdict(set)
	indegree = Counter()
	for _ in range(n - 1):
		(u, v) = rl()
		graph[u].add(v)
		graph[v].add(u)
		indegree[u] += 1
		indegree[v] += 1
	dc = 0
	done = False
	leaves = [i for i in range(1, n + 1) if indegree[i] == 1]
	for _ in range(k):
		if n - dc == 1 or n - dc == 2:
			res = 0
			done = True
			break
		nl = []
		for u in leaves:
			dc += 1
			v = graph[u].pop()
			indegree[v] -= 1
			graph[v] -= {u}
			if indegree[v] == 1:
				nl.append(v)
		leaves = nl
	print(res if done else n - dc)


from collections import deque
import sys

def input():
	return sys.stdin.readline().rstrip()
t = int(input())
for _ in range(t):
	flag = True
	waste = input()
	(n, k) = map(int, input().split())
	tree = [[0, set()] for z in range(n + 1)]
	for z in range(n - 1):
		(x, y) = map(int, input().split())
		tree[x][1].add(y)
		tree[y][1].add(x)
	leaf = deque([])
	tmp_leaf = deque([])
	for idx in range(n + 1):
		if len(tree[idx][1]) == 1:
			leaf.append(idx)
	sol = 0
	while k:
		while leaf:
			idx = leaf.popleft()
			if tree[idx][1]:
				parent = list(tree[idx][1])[0]
				tree[idx][1].remove(parent)
			if tree[parent][1]:
				tree[parent][1].remove(idx)
				tree[parent][0] = max(tree[parent][0], tree[idx][0] + 1)
				sol += 1
			if len(tree[parent][1]) == 1:
				tmp_leaf.append(parent)
		if not tmp_leaf:
			print(0)
			flag = False
			break
		leaf = tmp_leaf
		tmp_leaf = deque([])
		k -= 1
	if flag:
		print(n - sol)


import queue
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	input()
	(n, k) = map(int, input().split())
	l = [[] for i in range(n)]
	deg = [0] * n
	dis = [1000000000.0] * n
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		l[u - 1].append(v - 1)
		l[v - 1].append(u - 1)
	q = queue.Queue()
	for i in range(n):
		deg[i] = len(l[i])
		if deg[i] <= 1:
			dis[i] = 0
			q.put(i)
	while not q.empty():
		u = q.get()
		for v in l[u]:
			deg[v] -= 1
			if deg[v] == 1:
				dis[v] = dis[u] + 1
				q.put(v)
	print(sum((1 for i in dis if i >= k)))


import queue
test = int(input())
for _ in range(test):
	blank = str(input())
	(P, k) = map(int, input().split())
	graph = [[] for _ in range(P)]
	for _ in range(P - 1):
		(u, v) = map(int, input().split())
		graph[u - 1].append(v - 1)
		graph[v - 1].append(u - 1)
	deg = [0] * P
	dis = [1000000000.0] * P
	q = queue.Queue()
	for i in range(P):
		deg[i] = len(graph[i])
		if deg[i] <= 1:
			dis[i] = 0
			q.put(i)
	while not q.empty():
		u = q.get()
		for v in graph[u]:
			deg[v] -= 1
			if deg[v] == 1:
				dis[v] = dis[u] + 1
				q.put(v)
	print(sum((1 for i in dis if i >= k)))


from queue import Queue
for _ in range(int(input())):
	uu = input()
	(n, k) = map(int, input().split())
	graph = {}
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		if a not in graph:
			graph[a] = set()
		if b not in graph:
			graph[b] = set()
		graph[a].add(b)
		graph[b].add(a)
	if n <= 2:
		print(0)
		continue
	q = Queue()
	for ke in graph:
		neighbours = len(graph[ke])
		if neighbours == 1:
			q.put(ke)
	while q.qsize():
		for i in range(q.qsize()):
			curr = q.get()
			n -= 1
			for neighbour in graph[curr]:
				graph[neighbour].remove(curr)
				if len(graph[neighbour]) == 1:
					q.put(neighbour)
		k -= 1
		if k == 0 or n == 0:
			break
	print(n)