Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1486
Color the Tree

Time Limit: 2 Seconds      Memory Limit: 65536 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



Author: DU, Peng
Source: ZOJ Monthly, February 2003
Submit    Status