Tree Coloring

A tree is a connected undirected graph with no cycle. You are given a tree with $N$ nodes and $N-1$ edges. You want to color the tree, that is, give every node one color from $\{1, 2, \dots, K\}$ so that two nodes joined by an edge always get different colors.

Write a program that counts how many colorings there are. The count can be very large, so print it modulo $93563$.

The first line contains the number of test cases $T$ ($1 \le T \le 10$). Then $T$ test cases follow, each in this format.

• The first line of a test case contains two integers $N$ and $K$. $N$ is the number of nodes ($2 \le N \le 200$) and $K$ is the number of colors you may use ($1 \le K \le 10$). The nodes are numbered from $1$ to $N$.
• Each of the next $N-1$ lines describes one edge of the tree with two integers $A$ and $B$ ($1 \le A \le N$; $1 \le B \le N$; $A \ne B$), meaning an edge joins node $A$ and node $B$.

Print $T$ lines. For each test case, print the number of colorings modulo $93563$ on one line, in input order.