Ага, вот: «Особые приметы: очень любит рыбий жир, при звуках флейты... теряет волю».
Коллега и Шеф готовятся к операции по захвату слона. Они уже раздобыли индийскую флейту, а сейчас пытаются усилить запах рыбьего жира. Шефу известно, что органическая структура рыбьего жира состоит из двух деревьев, по $$$n$$$ молекул в каждом. Напомним, что деревом называется связный неориентированный граф без циклов.
Шеф хочет провести ровно одно ребро, соединяющее какую-то молекулу первого дерева с какой-то молекулой второго. Запах усилится, если после добавления такого ребра расстояние между любыми двумя молекулами не превосходит $$$k$$$. Расстояние между молекулами определяется как минимальное количество рёбер, которые надо пройти от одной молекулы до другой.
Помогите Шефу посчитать количество способов провести ребро, чтобы запах рыбьего жира усилился.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора даны два целых числа $$$n$$$, $$$k$$$ ($$$2 \le n \le 10^5, 2 \le k \le 2n$$$) — количество вершин в каждом дереве и максимальное расстояние между молекулами.
В следующих $$$n - 1$$$ строках каждого набора даны пары чисел $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — рёбра между молекулами в первом дереве.
В следующих $$$n - 1$$$ строках каждого набора даны пары чисел $$$c_i, d_i$$$ ($$$1 \le c_i, d_i \le n$$$) — рёбра между молекулами во втором дереве.
Для каждого набора входных данных гарантируется, что наборы рёбер задают корректные деревья.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Выведите количество способов провести ребро, чтобы усилить запах рыбьего жира.
34 41 21 31 42 12 34 33 31 22 33 21 39 68 38 42 13 52 67 69 49 78 38 68 24 88 78 18 59 8
210
Рассмотрим все способы провести ребро, чтобы усилить запах в первом наборе входных данных:
