Color the Tree

Time Limit: 1 Second    Memory Limit: 32768 KB

Given a tree with n nodes (which are represented by numbers from 1 to n) and m colors. How many different ways are there to color the nodes so that none of two neighboring nodes have the same color?

Input

There are several test cases.

For each test case, the first line contains two positive integers n (1 <= n <= 50) and m (2 <= m <= 20).

The next n-1 lines each gives the indices of two nodes that are connected by an edge and hence describe the structure of a tree.

The input is terminated with 0 0.

Output

For each test case print in a single line the number of different coloring ways.

Sample Input

2 2
1 2
0 0

Sample Output

2

Submit

Source: ZOJ Monthly, February 2003