eolymp
bolt
Try our new interface for solving problems
Problems

Distance in Tree

Distance in Tree

Time limit 2 seconds
Memory limit 256 MiB

A connected graph without cycles is called a tree.

The distance between two vertices of a tree is defined as the length (in edges) of the shortest path between these vertices.

Given a tree with n vertices and a positive integer k. Compute the number of distinct pairs of vertices of the tree whose distance is equal to k. Note that pairs (v, u) and (u, v) are considered the same pair.

Input data

The first line contains two integers n and k~(1 \le n \le 50000, 1 \le k \le 500) — the number of vertices in the tree and the required distance between vertices.

The next n - 1 lines contain the edges of the tree in the format a_i~b_i~(1 \le a_i, b_i \le n, a_i \neq b_i), where a_i and b_i are the vertices of the tree connected by the i-th edge. All specified edges are different.

Output data

Print a single integer — the number of distinct pairs of tree vertices whose distance is equal to k.

Examples

Input example #1
5 2
1 2
2 3
3 4
2 5
Output example #1
4
Source VK Cup 2012 Round 1, Problem D