Welcome to ZOJ
Select Problem
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?


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.

Sample Input

2 2
1 2
0 0

Sample Output


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