Dấu Chân Trên Các Đỉnh

Cho một cây gồm $n$ đỉnh, đánh số từ $1$ đến $n$. Có $m$ cặp đỉnh $(u_i,v_i)$; mỗi cặp xác định đường đi đơn duy nhất giữa hai đỉnh đó.

Một đỉnh được xem là nằm trên đường đi nếu nó xuất hiện ở bất kỳ vị trí nào của đường, kể cả hai đầu mút. Với mỗi đỉnh $x$, hãy đếm có bao nhiêu trong $m$ đường đi chứa $x$.

Input

• Dòng đầu chứa hai số nguyên $n,m$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a,b$, biểu diễn một cạnh của cây.
• $m$ dòng cuối, mỗi dòng chứa hai số nguyên $u,v$, biểu diễn một đường đi cần tính. Hai đầu mút được phép trùng nhau.

Output

• In $n$ số nguyên trên một dòng. Số thứ $x$ là số đường đi chứa đỉnh $x$, với $1\le x\le n$.

Constraints

• $1\le n,m\le 2\cdot 10^5$.
• $1\le a,b,u,v\le n$; $a\ne b$ trên mỗi cạnh.
• $n-1$ cạnh tạo thành một cây.
• Input chỉ chứa một test case.

Scoring

• Subtask $1$ ($50$ điểm): $n,m\le 2000$.
• Subtask $2$ ($50$ điểm): không có giới hạn bổ sung.

Example

7 5
1 2
1 3
2 4
2 5
3 6
6 7
4 5
4 7
2 6
3 3
5 7

3 4 4 2 2 3 2