E. Вырезание графа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На день рождения юному Феде подарили дерево из $$$n$$$ вершин и бензопилу. Он хочет вырезать из него связанный подграф. Федя решил действовать следующим образом: он выбирает три различные вершины $$$a, b, c$$$ ($$$a \lt b \lt c$$$) и вырезает минимальный связный подграф, содержащий все три вершины. При этом он хочет, чтобы размер получившегося подграфа был ровно $$$d$$$ (то есть число вершин в вырезанном подграфе должно быть равно $$$d$$$).

Ему стало интересно, сколько различных таких подграфов он сможет вырезать. Подграфы называются различными, если выбранные тройки вершин не совпадают. Помогите ему справиться с этой задачей!

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержатся два числа $$$n$$$ и $$$d$$$ ($$$3 \le d \leq n \le 2000$$$) — число вершин в дереве и желаемый размер вырезанного подграфа.

Затем следуют $$$n - 1$$$ строка, в каждой из которых заданы два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), означающие вершины, соединённые очередным ребром. Гарантируется, что данный граф является деревом.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.

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

Для каждого набора входных данных выведите единственное число — количество различных подграфов, которые может вырезать Федя.

Пример
Входные данные
3
4 3
1 2
3 1
4 1
5 5
1 2
2 4
2 3
5 1
7 7
1 2
1 3
2 4
2 5
3 6
3 7
Выходные данные
3
1
0
Примечание

Так выглядит дерево для первого набора входных данных:

Подходят следующие тройки: ($$$1, 2, 3$$$), ($$$1, 2, 4$$$), ($$$1, 3, 4$$$). А для тройки ($$$2, 3, 4$$$) размер связанного подграфа будет равен $$$4$$$.

Так выглядит дерево для второго набора входных данных:

И для него подходит только тройка вершин ($$$3, 4, 5$$$).

Так выглядит дерево для третьего набора входных данных:

Можно показать, что для данного подграфа не подходит ни одна тройка.