#10028. DDD - Đếm đường đi

Cây là đồ thị vô hướng liên thông có số cạnh nhỏ hơn số đỉnh. Cho một cây gồm n đỉnh và n - 1 cạnh và một số nguyên dương p. Với mỗi đỉnh u, bạn hãy đếm số đỉnh v sao cho số cạnh trên đường đi ngắn nhất giữa u và v chia hết cho p. Số cạnh trên đường đi giữa u và u là 0.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên  — số đỉnh của cây và số nguyên p (1 ≤ p ≤ 30). n - 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên và cho biết có một cạnh nối đỉnh u và đỉnh v trên cây.

Dữ liệu ra

In ra n số nguyên, số thứ i là số đỉnh j sao cho số cạnh trên đường đi ngắn nhất từ i tới j chia hết cho p. Các số được viết trên một dòng, cách nhau bởi dấu cách.

Ví dụ

//Input
11 4
6 2
6 5
10 9
8 6
5 4
5 1
4 11
6 7
5 10
2 3

//Output
2 3 4 2 1 1 3 3 5 2 5 

//Input
11 7
3 5
6 11
4 8
7 6
1 2
9 7
5 4
9 10
4 1
4 10

//Output
1 2 2 1 1 1 1 1 1 1 3 

Giới hạn

• Subtask 1 (30 điểm): n ≤ 5000
• Subtask 2 (10 điểm): p = 1
• Subtask 3 (20 điểm): p = 2
• Subtask 4 (40 điểm): Không có ràng buộc gì thêm.