Đường đi của những kẻ ngốc

Berland có $n$ thành phố, được nối bởi $n-1$ con đường hai chiều sao cho giữa mỗi cặp thành phố có duy nhất một đường đi đơn (tức là đồ thị tạo thành một cây). Các con đường được đánh số từ $1$ tới $n-1$ theo thứ tự xuất hiện trong dữ liệu vào.

Có $k$ cặp người, cặp thứ $i$ gồm hai người sống ở thành phố $a_i$ và $b_i$. Người thứ $2i-1$ đi từ thành phố $a_i$ tới gặp người thứ $2i$ ở thành phố $b_i$ theo đường đi đơn duy nhất trong cây.

Với mỗi con đường, hãy đếm xem có bao nhiêu người đã đi qua nó. Một con đường được tính nếu nó nằm trên đường đi đơn của ít nhất một trong hai người trong một cặp; cặp $(a_i,b_i)$ đóng góp giá trị $2$ cho mỗi con đường nằm trên đường đi từ $a_i$ tới $b_i$ (mỗi người đi qua đúng một lần).

Lưu ý: nếu $a_i=b_i$ thì không có con đường nào được sử dụng trong cặp đó.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số thành phố.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$) mô tả con đường nối hai thành phố $u_i$ và $v_i$.
• Dòng tiếp theo chứa số nguyên $k$ — số cặp người.
• $k$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i,b_i$ ($1\le a_i,b_i\le n$).

Dữ liệu ra

In ra $n-1$ số nguyên cách nhau bởi khoảng trắng: số thứ $i$ là số người đã đi qua con đường thứ $i$ (theo thứ tự xuất hiện trong dữ liệu vào).

Ràng buộc

• $2\le n\le {10}^5$
• $0\le k\le {10}^5$

Ví dụ