D. Расстояние в дереве
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
512 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Деревом называется связный граф, не содержащий циклов.

Расстоянием между двумя вершинами дерева называется длина (в ребрах) кратчайшего пути между этими вершинами.

Дано дерево из n вершин и положительное число k. Посчитайте количество различных пар вершин дерева, расстояние между которыми равно k. Обратите внимание, что пары (v, u) и (u, v) считаются одной и той же парой.

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

В первой строке записаны два целых числа n и k (1 ≤ n ≤ 50000, 1 ≤ k ≤ 500) — количество вершин дерева и требуемое расстояние между вершинами.

В следующих n - 1 строках записаны ребра дерева в формате «ai bi» (без кавычек) (1 ≤ ai, bi ≤ n, ai ≠ bi), где ai и bi — вершины дерева, соединенные i-м ребром. Все заданные ребра различны.

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

Выведите единственное целое число — количество различных пар вершин дерева, расстояние между которыми равно k.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

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

В первом примере парами вершин, расстояние между которыми равно 2, будут пары (1, 3), (1, 5), (3, 5) и (2, 4).