E. Садовник и дерево
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дерево — это неориентированный связный граф, в котором отсутствуют циклы. В этой задаче речь идет о некорневых деревьях.

Лист дерева — это вершина, которая соединена не более чем с одной другой вершиной.

Садовник Виталий вырастил дерево из $$$n$$$ вершин. Он решил подстричь дерево. Для этого он совершает несколько операций. За одну операцию он удаляет все листья дерева.

Пример дерева.

Например, рассмотрим дерево, изображённое на рисунке выше. На рисунке ниже приведён результат применения к дереву ровно одной операции.

Результат применения операции «удалить все листья».

Обратите внимание на особенные случаи применения операций:

  • применение операции к пустому дереву (из $$$0$$$ вершин) не меняет его;
  • применение операции к дереву из одной вершины приводит к удалению этой вершины (т. е. одна эта вершина считается листом);
  • применение операции к дереву из двух вершин приводит к удалению обеих вершин (обе вершины считаются листьями).

Виталий применил к дереву последовательно $$$k$$$ операций. Сколько вершин в нём осталось?

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

Перед каждым набором входных данных расположена пустая строка.

Каждый набор данных состоит из нескольких строк. Первая строка набора данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 4 \cdot 10^5$$$, $$$1 \le k \le 2 \cdot 10^5$$$) — количество вершин в дереве и количество операций. Далее идут $$$n - 1$$$ строк, каждая содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — две вершины, которые соединены ребром. Гарантируется, что заданный граф является деревом, в нём отсутствуют петли и кратные рёбра. Гарантируется, что сумма $$$n$$$ из всех наборов входных данных не превосходит $$$4 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке одно целое число — количество вершин, которое осталось в дереве после применения $$$k$$$ операций.

Пример
Входные данные
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
Выходные данные
7
0
0
3
1
2
Примечание

Первый набор входных данных разобран в условии.

Во втором наборе задано дерево из двух вершин. К нему применяются $$$200000$$$ операций. Первая удаляет обе вершины, остальные операции не изменяют дерево.

В третьем наборе входных данных дано дерево из трёх вершин. В результате применения первой операции в нём остаётся всего $$$1$$$ вершина (с номером $$$2$$$), в результате второй операции дерево становится пустым.