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?

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.

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