树是不包含任何循环的连通图。
树的两个顶点之间的距离是这些顶点之间的最短路径的长度(以边为单位)。
给你一棵有 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 说明符。
示例
输入 #1
5 2 1 2 2 3 3 4 2 5
输出 #1
4
输入 #2
5 3 1 2 2 3 3 4 4 5
输出 #2
2
注意
在第一个样本中,彼此距离为 2 的顶点对为 (1, 3)、(1, 5)、(3, 5) 和 (2, 4)。