题目描述

愚蠢之岛有两个问题，傻瓜和道路。这里有 $n$ 个城市通过道路连接，由傻瓜居住，每对城市之间都有一条路（否则傻瓜会不高兴）。此外，每对城市之间只有一条简单的路径（否则傻瓜会迷路）。

傻瓜有时会互相拜访，但是他们不聪明，所以他们总是只走简单的路径。

简单路径是指每条路最多走一次的路径。

请你帮助这里的政府计算出每条路被傻瓜们走了多少次。

注意需要按照每条边输入的顺序输出。

输入格式

第一行一个整数 $n (2 \le n \le 10^5)$ — 城市的个数。

接下来的 $n - 1$ 行包含两个整数 $u_i, v_i (1 \le u_i, v_i \le n, u_i \neq 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$ 个整数，数据间用空格隔开。第 $i$ 个数表示这条边共被走了多少次。输出的顺序与边输入的顺序一致。

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$ 号、$2$ 号和 $3$ 号傻瓜都走了第一条路，$3$ 号傻瓜走了第二条路，$2$ 号傻瓜走第三条路，$1$ 号傻瓜走了第四条路。