Fools and Roads

Description:

Input:

The first line contains a single integer n (2 ≤ n ≤ 10⁵) — the number of cities.

Each of the next n - 1 lines contains two space-separated integers u_i, v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i), that means that there is a road connecting cities u_i and v_i.

The next line contains integer k (0 ≤ k ≤ 10⁵) — the number of pairs of fools who visit each other.

Next k lines contain two space-separated numbers. The i-th line (i > 0) contains numbers a_i, b_i (1 ≤ a_i, b_i ≤ n). That means that the fool number 2i - 1 lives in city a_i and visits the fool number 2i, who lives in city b_i. The given pairs describe simple paths, because between every pair of cities there is only one simple path.

Output:

Print n - 1 integer. The integers should be separated by spaces. The i-th number should equal the number of fools who can go on the i-th road. The roads are numbered starting from one in the order, in which they occur in the input.

Sample Input:

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

Sample Output:

2 1 1 1 

Sample Input:

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

Sample Output:

3 1 1 1 

Note:

In the first sample the fool number one goes on the first and third road and the fool number 3 goes on the second, first and fourth ones.

In the second sample, the fools number 1, 3 and 5 go on the first road, the fool number 5 will go on the second road, on the third road goes the fool number 3, and on the fourth one goes fool number 1.