Tính Lưu Lượng Mạng

Một mạng máy tính gồm $n$ máy chủ được kết nối bởi $n - 1$ đường truyền hai chiều. Cấu trúc mạng đảm bảo giữa hai máy chủ bất kỳ luôn tồn tại đúng một đường đi đơn, nghĩa là không đi qua bất kỳ máy chủ nào quá một lần.

Trong quá trình hoạt động, hệ thống thực hiện $k$ yêu cầu truyền dữ liệu. Mỗi yêu cầu sẽ truyền dữ liệu giữa hai máy chủ thông qua đường đi đơn duy nhất kết nối hai máy chủ đó.

Hãy tính số lần dữ liệu được truyền qua từng đường truyền trong toàn bộ hệ thống.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ ($2 ≤ n ≤ 10^5$), đại diện cho số lượng máy chủ.

Trong $n - 1$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i$ và $v_i$ ($1 ≤ u_i, v_i ≤ n, u_i ≠q v_i$), mô tả đường truyền kết nối giữa máy chủ $u_i$ và máy chủ $v_i$.

Dòng tiếp theo chứa số nguyên $k$ ($0 ≤ k ≤ 10^5$), đại diện cho số lượng yêu cầu truyền dữ liệu.

Trong $k$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$ ($1 ≤ a_i, b_i ≤ n$), biểu thị yêu cầu truyền dữ liệu giữa máy chủ $a_i$ và máy chủ $b_i$.

Kết quả

In ra $n - 1$ số nguyên trên một dòng, phân tách bằng dấu cách. Số thứ $i$ tương ứng với số lượt truyền dữ liệu đi qua đường truyền thứ $i$. Thứ tự các đường truyền được đánh số từ $1$ đến $n - 1$ theo đúng thứ tự xuất hiện trong dữ liệu vào.

Chấm điểm

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

Subtask 2 (70 points). $2 ≤ n ≤ 10^5$

Ví dụ

Input

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

Output

1 2 1

Ghi chú

Trong ví dụ trên, yêu cầu thứ nhất gửi dữ liệu giữa máy chủ $1$ và $3$ đi qua đường truyền thứ $1$ và đường truyền thứ $2$. Yêu cầu thứ hai gửi dữ liệu giữa máy chủ $2$ và $4$ đi qua đường truyền thứ $2$ và đường truyền thứ $3$.