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.