무지개 트리

시간 제한5초메모리 제한512 MB

요약

작은 트리의 간선을 k가지 색으로 칠할 때, 경로 위 연속한 두 개와 세 개의 간선이 모두 다른 색이 되는 채색의 수를 세어 1e9+9로 나눈 나머지를 구한다.

문제

그래프 이론에서 트리는 사이클이 없는 연결 무향 단순 그래프다. 정점이 $n$ 개인 트리의 간선은 항상 $n - 1$ 개다.

트리에서 경로는 서로 다른 간선을 이어 붙인 수열이다. 수열에서 연속한 두 간선은 정점 하나를 공유한다.

정점이 $n$ 개, 간선이 $n - 1$ 개인 트리가 주어진다. 각 간선을 $k$ 가지 색 중 하나로 칠할 수 있다.

간선 2개로 이루어진 모든 경로와 간선 3개로 이루어진 모든 경로에서 간선의 색이 모두 다르면, 그 색칠을 무지개 색칠이라고 한다. 즉 연속한 두 간선의 색이 서로 다르고, 연속한 세 간선의 색도 서로 다르다.

트리와 색의 개수 $k$ 가 주어질 때, 무지개 색칠의 개수를 $1000000009$ 로 나눈 나머지를 구한다.

첫째 줄에 테스트 케이스의 개수 $C$ 가 주어진다. 이어서 각 테스트 케이스가 다음 형식으로 주어진다.

첫째 줄에 두 정수 $n$ 과 $k$ 가 주어진다. $n$ 은 트리의 정점 개수, $k$ 는 사용할 수 있는 색의 개수다.
다음 $n - 1$ 개 줄에 간선이 하나씩 주어진다. 각 줄의 두 정수 $x$ 와 $y$ 는 정점 $x$ 와 정점 $y$ 를 잇는 간선을 뜻한다. 정점 번호는 1부터 $n$ 까지다.

제한

각 테스트 케이스마다 한 줄에 Case #X: Y 형식으로 출력한다. $X$ 는 1부터 시작하는 테스트 케이스 번호이고, $Y$ 는 그 테스트 케이스의 답이다.

첫 번째 예제 케이스의 트리는 정점이 4개이고, 세 간선이 한 정점에서 모두 만난다. 세 간선은 서로 인접하므로 무지개 색칠에서는 색이 모두 달라야 하고, 색칠 방법은 $10 \times 9 \times 8 = 720$ 가지다.

두 번째 예제 케이스의 트리는 간선 4개로 이루어진 경로이고 색은 3가지다. 앞의 세 간선은 색이 모두 달라야 하므로 $3 \times 2 \times 1$ 가지로 칠하고, 네 번째 간선에 쓸 색은 하나만 남는다. 따라서 무지개 색칠은 6가지다.

예제 1

입력

예상 출력

Case #1: 720
Case #2: 6

예제 2

입력

4
2 1
1 2
2 1000000000
1 2
3 1
1 2
2 3
3 2
2 3
1 2

예상 출력

Case #1: 1
Case #2: 1000000000
Case #3: 0
Case #4: 2