4350 - 第九课:路径覆盖统计

给出一棵树,再给出k条树上的简单路径,求每条边被不同的路径覆盖了多少次。

输入

第一行有一个整数$ n (2 \le n \le 10^5) $, 表示树的结点数目。

接下来$ n-1 $ 行,每行给出两个整数$ u_i, v_i (1 \le u_i, v_i \le n, u_i \ne v_i)$,表示$ u_i, v_i $之间有一条边直接相连。

接下来给出一个整数$ k (0 \le k \le 10^5) $。

接下来k行,每行给出两个整数$ a_i, b_i (1 \le a_i, b_i \le n)$,表示$ a_i, b_i $之间有一条路径。

输出

输出$ n-1 $个整数,表示每一条边被路径覆盖的次数。

样例

输入

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

输出

2 1 1 1

输入

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

输出

3 1 1 1
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题