Cây của chú voi con

Cho một cây có gốc gồm $n$ đỉnh, đánh số từ $1$ đến $n$, với gốc tại đỉnh $1$. Ban đầu, danh sách số tại mỗi đỉnh đều rỗng.

Có $m$ thao tác. Thao tác thứ $i$ (với $1\le i\le m$) cho hai đỉnh $a_i$ và $b_i$: thêm số $i$ vào danh sách của tất cả các đỉnh thuộc cây con có gốc là $a_i$, sau đó thêm số $i$ vào danh sách của tất cả các đỉnh thuộc cây con có gốc là $b_i$.

Sau khi thực hiện hết các thao tác, với mỗi đỉnh $i$ hãy đếm $c_i$ — số đỉnh $j$ ($1\le j\le n$, $j\ne i$) sao cho danh sách của đỉnh $i$ và đỉnh $j$ có ít nhất một số chung.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$ mô tả một cạnh của cây nối hai đỉnh $u_i$ và $v_i$ ($u_i\ne v_i$).
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$ ($a_i\ne b_i$) — hai đỉnh của thao tác thứ $i$.

Dữ liệu đảm bảo đồ thị đã cho là một cây vô hướng.

Dữ liệu ra

In ra trên một dòng $n$ số nguyên $c_1,c_2,\dots ,c_n$ cách nhau bởi dấu cách.

Ràng buộc

• $1\le n,m\le {10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• $1\le a_i,b_i\le n$, $a_i\ne b_i$

Ví dụ