Деревом называется связный граф, не содержащий циклов.
Расстоянием между двумя вершинами дерева называется длина (в ребрах) кратчайшего пути между этими вершинами.
Дано дерево из n вершин и положительное число k. Посчитайте количество различных пар вершин дерева, расстояние между которыми равно k. Обратите внимание, что пары (v, u) и (u, v) считаются одной и той же парой.
Выходные данные
Выведите единственное целое число — количество различных пар вершин дерева, расстояние между которыми равно k.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом примере парами вершин, расстояние между которыми равно 2, будут пары (1, 3), (1, 5), (3, 5) и (2, 4).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
1 2
2 3
3 4
2 5
|
4
|
|
2
|
5 3
1 2
2 3
3 4
4 5
|
2
|