#46. Cầu vồng (Mã bài: RAINBOW)

Cho một cây gồm đỉnh, bạn cần phải tô màu cạnh của cây bằng các màu từ 1 đến sao cho:

• Mọi đường đi độ dài 2 đều có màu cầu vồng.
• Mọi đường đi độ dài 3 đều có màu cầu vồng.

Một đường đi có màu cầu vồng khi và chỉ khi tất cả các cạnh nằm trên đường đi có màu deep blue một khác nhau.

Yêu cầu: Hãy đếm số cách tô màu cho cây.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên dương () và ().
• dòng tiếp theo, mỗi dòng chứa hai số nguyên dương và thể hiện có cạnh nối giữa hai đỉnh và .

Kết quả: Ghi ra số cách tô màu sau khi chia lấy dư cho .

Ví dụ:

Dữ liệu:

4 10
1 2
1 3
1 4

Kết quả:

720

Dữ liệu:

5 3
1 2
2 3
3 4
4 5

Kết quả:

6

Giới hạn:

• Subtask 1 (10%): ;
• Subtask 2 (10%): và cây có dạng cây nghị phân đầy đủ;
• Subtask 3 (20%): ;
• Subtask 4 (20%): các nút có bậc không quá 3;
• Subtask 5 (30%): ;
• Subtask 6 (10%): không có ràng buộc gì thêm.