Coding is the closest thing we have to superpower ！

3590 : 树进阶-路径覆盖统计
描述

给出一棵树,再给出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
标签
树 差分 LCA
语言：
主题：
登录以提交代码;