Total Domination in Trees

An alien mothership can be modeled as an undirected tree with n nodes and n-1 edges, where the nodes are numbered from 1 to n. JYY has k surveillance devices. Placing a device at a node u allows JYY to monitor the communications on every edge incident to u (i.e. all nodes directly adjacent to u are monitored), but note that the communications at u itself are not monitored by the device at u.

A placement of devices is valid if and only if every node in the tree is monitored by at least one device placed at one of its neighbors. In addition, each node can have at most one device and all k devices must be used. Your task is to count the number of different ways to choose exactly k nodes to place the devices so that every node is monitored.

Note: If a node has a device, it must also have at least one other neighbor with a device (its own device does not cover it). Hence, the set of nodes with devices forms a total dominating set of the tree.

The answer can be large; output the exact count.

Hint: Consider a DFS tree DP solution. When a node is chosen to install a device, one must ensure that if its parent did not place a device then at least one of its children places a device (to cover it), and if a node is not chosen then its parent must have a device in order to cover it.

inputFormat

The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ n), representing the number of nodes in the tree and the number of surveillance devices, respectively. Each of the next n-1 lines contains two integers u and v (1 ≤ u, v ≤ n), indicating an undirected edge between node u and node v.

outputFormat

Output a single integer: the number of valid placements of the surveillance devices.

sample

2 2
1 2

1