Cụm Đen Chứa Đỉnh

Bạn được cho một cây gồm $n$ đỉnh. Mỗi đỉnh sẽ được tô đen hoặc trắng. Một cách tô được gọi là hợp lệ khi tập các đỉnh đen không rỗng và liên thông.

Với mỗi đỉnh $u$, hãy đếm số cách tô hợp lệ trong đó $u$ được tô đen. Vì kết quả có thể rất lớn, chỉ cần in phần dư khi chia cho $m$.

Hai cách tô khác nhau nếu tồn tại ít nhất một đỉnh có màu khác nhau.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Mỗi dòng trong $n-1$ dòng tiếp theo chứa hai số nguyên $u$ và $v$, mô tả một cạnh vô hướng của cây.

Output

• In $n$ dòng. Dòng thứ $u$ chứa số cách tô hợp lệ có đỉnh $u$ màu đen, lấy phần dư theo $m$.

Constraints

• $1\le n\le 10^5$.
• $2\le m\le 10^9$; $m$ không nhất thiết là số nguyên tố.
• $1\le u,v\le n$ và $u\ne v$.
• Các cạnh tạo thành một cây.
• Mỗi giới hạn trên áp dụng cho một test độc lập.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 15$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5 100
1 2
2 3
2 4
4 5

7
12
7
10
6