트리 색칠하기

트리는 연결되어 있고 사이클이 없는 무향 그래프이다. 노드 $N$개와 간선 $N-1$개로 이루어진 트리가 주어진다. 이 트리를 색칠하려고 한다. 즉, 각 노드에 $\{1, 2, \dots, K\}$ 중 한 가지 색을 배정하는데, 간선으로 이어진 두 노드는 색이 서로 달라야 한다.

색칠하는 방법이 몇 가지인지 세는 프로그램을 작성하시오. 가짓수가 매우 커질 수 있으므로 $93563$으로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10$)가 주어진다. 이어서 $T$개의 테스트 케이스가 다음 형식으로 주어진다.

• 각 테스트 케이스의 첫째 줄에 정수 $N$과 $K$가 주어진다. $N$은 노드의 개수 ($2 \le N \le 200$), $K$는 쓸 수 있는 색의 개수 ($1 \le K \le 10$)이다. 노드 번호는 $1$부터 $N$까지이다.
• 다음 $N-1$개 줄에 트리의 간선이 주어진다. 각 줄에는 정수 $A$와 $B$ ($1 \le A \le N$; $1 \le B \le N$; $A \ne B$)가 주어지고, 노드 $A$와 노드 $B$를 잇는 간선이 있다는 뜻이다.

$T$개의 줄을 출력한다. 각 테스트 케이스마다 색칠하는 방법의 수를 $93563$으로 나눈 나머지를 입력 순서대로 한 줄에 하나씩 출력한다.