Rung Động

Ngay từ khoảnh khắc ánh mắt chạm nhau lần đầu tiên giữa quán cà phê đông đúc, một sợi dây cảm xúc kỳ diệu đã kết nối các điểm hẹn trong thành phố. Mạng lưới các điểm hẹn gồm $n$ địa điểm được đánh số từ $1$ đến $n$. Giữa $n$ địa điểm này có đúng $n-1$ lối đi hai chiều kết nối trực tiếp sao cho giữa hai điểm bất kỳ luôn có một con đường duy nhất để di chuyển.

Mỗi khi nhịp tim đập liên hồi vì xao xuyến, một hành trình trao gửi thư tình lại được tạo ra giữa hai địa điểm $a$ và $b$, đi qua tuyến đường ngắn nhất nối hai điểm đó. Tổng cộng có $m$ hành trình tình yêu như vậy đã diễn ra. Với mỗi địa điểm, hãy đếm số lượng hành trình tình yêu có đi qua địa điểm đó.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1 ≤ n, m ≤ 2 · 10^5$), lần lượt là số lượng địa điểm và số lượng hành trình tình yêu.

$n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ ($1 ≤ a, b ≤ n$), thể hiện có lối đi trực tiếp giữa địa điểm $a$ và địa điểm $b$.

$m$ dòng cuối cùng, mỗi dòng chứa hai số nguyên $a$ và $b$ ($1 ≤ a, b ≤ n$), thể hiện một hành trình tình yêu nối giữa hai địa điểm $a$ và địa điểm $b$.

Kết quả

In ra $n$ số nguyên trên một dòng, số thứ $i$ cho biết số lượng hành trình tình yêu có đi qua địa điểm $i$.

Chấm điểm

Subtask 1 (30 points). $n, m ≤ 2000$

Subtask 2 (30 points). Cây có dạng đặc biệt (đường thẳng, ngôi sao) hoặc các hành trình có cấu trúc đặc biệt.

Subtask 3 (40 points). $1 ≤ n, m ≤ 2 · 10^5$

Ví dụ

Input

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

Output

1 2 2 1

Ghi chú

Giải thích ví dụ:

Hành trình thứ nhất nối giữa địa điểm 1 và địa điểm 3 gồm các địa điểm: 1, 2, 3.

Hành trình thứ hai nối giữa địa điểm 3 và địa điểm 4 gồm các địa điểm: 3, 2, 4.

Số lần xuất hiện của các địa điểm 1, 2, 3, 4 lần lượt là 1, 2, 2, 1.