Cho một cây có \(n\) nút, các nút trên cây được đánh số lần lượt là \(1,2,3,...,n\) và \(m\) con đường.

Nhiệm vụ của bạn là với mỗi nút, hãy đếm số đường đi chứa nút này.

Input

• Dòng đầu tiên chứa 2 số \(n\) và \(m\)
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa chứa 2 số \(a\) và \(b\), thể hiện rằng có một cạnh nối hai nút \(a\) và \(b\)
• \(m\) dòng cuối, mỗi dòng chứa 2 số \(a\) và \(b\), thể hiện rằng có một con đường từ nút \(a\) tới \(b\)

Constraints

• \(1 \leq n, m \leq 2 \cdot 10^5\)
• \(1 \leq a, b \leq n\)

Output

• In ra \(n\) số: số lượng đường đi qua mỗi nút \(1,2,3,\dots,n\)

Example

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

3 1 3 1 1