Given a tree T with n nodes, how many subtrees (T') of T have at most K edges connected to (T - T')?

Input Format

The first line contains two integers n and K followed by n-1 lines each containing two integers a & b denoting that there's an edge between a & b.

Constraints

1 <= K <= n <= 50

Every node is indicated by a distinct number from 1 to n.

Output Format

A single integer which denotes the number of possible subtrees.

Sample Input
3 1
2 1
2 3

Sample Output
6

Explanation

There are 2^3 possible sub-trees:

{} {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}

But:

the sub-trees {2} and {1,3} are not valid.
{2} isn't valid because it has 2 edges connecting to it's complement {1,3} whereas K = 1 in the sample test-case
{1,3} isn't valid because, well, it's not a sub-tree. The nodes aren't connected.

见题面

见题面