Trong lý thuyết đồ thị, một cây là một đồ thị đơn vô hướng, liên thông và không có chu trình. Một cây có \(n\) nút luôn có \(n - 1\) cạnh.

Một đường đi trong cây là một dãy các cạnh phân biệt liên tiếp nhau (mỗi cặp cạnh liên tiếp trong đường đi chia sẻ chung một đỉnh).

Xét một cây có \(n\) đỉnh và \(n - 1\) cạnh. Bạn có thể tô mỗi cạnh bằng một trong \(k\) màu.

Một cách tô màu các cạnh được gọi là tô màu cầu vồng (rainbow coloring) nếu trong mọi đường đi có độ dài 2 hoặc 3 cạnh, màu của các cạnh đều khác nhau. (Nghĩa là, cứ hai cạnh liên tiếp bất kỳ phải có màu khác nhau, và cứ ba cạnh liên tiếp bất kỳ phải có màu khác nhau).

Cho một cây và số lượng màu \(k\), hãy tìm số cách tô màu cầu vồng modulo \(1000000009\).

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(C\). Sau đó, với mỗi bộ trong số \(C\) bộ test:

• Một dòng chứa hai số nguyên theo định dạng "\(n\) \(k\)". \(n\) là số nút trong cây, và \(k\) là số màu có sẵn.
• \(n - 1\) dòng, mỗi dòng cho một cạnh, chứa hai số nguyên "\(x\) \(y\)", cho biết có một cạnh giữa nút \(x\) và nút \(y\). Các nút được đánh số từ 1 đến \(n\).

Dữ liệu ra

Với mỗi bộ test, xuất một dòng. Dòng đó phải chứa "Case #\(X\): \(Y\)", trong đó \(X\) là số thứ tự của bộ test (bắt đầu từ 1) và \(Y\) là đáp án cho bộ test đó.

Ràng buộc

• \(1 \le k \le 1000000000\).
• Tất cả các số hiệu nút nằm trong khoảng từ 1 đến \(n\), bao gồm cả hai đầu mút.

Phân nhóm

• Small dataset (Test set 1): \(1 \le C \le 100\); \(2 \le n \le 20\).
• Large dataset (Test set 2): \(1 \le C \le 40\); \(2 \le n \le 500\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
4 10
1 2
1 3
1 4
5 3
1 2
2 3
3 4
4 5

Case #1: 720
Case #2: 6

Nguồn

Google Code Jam 2008, Vòng bán kết EMEA, bài Rainbow Trees.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.