CF191C.Fools and Roads

They say that Berland has exactly two problems, fools and roads. Besides, Berland has n cities, populated by the fools and connected by the roads. All Berland roads are bidirectional. As there are many fools in Berland, between each pair of cities there is a path (or else the fools would get upset). Also, between each pair of cities there is no more than one simple path (or else the fools would get lost).

But that is not the end of Berland's special features. In this country fools sometimes visit each other and thus spoil the roads. The fools aren't very smart, so they always use only the simple paths.

A simple path is the path which goes through every Berland city not more than once.

The Berland government knows the paths which the fools use. Help the government count for each road, how many distinct fools can go on it.

Note how the fools' paths are given in the input.

人们说，贝尔兰只有两个问题：傻瓜和道路。此外，贝尔兰有 $n$ 座城市，由傻瓜居住，并通过道路相互连接。贝尔兰的所有道路都是双向的。由于贝尔兰的傻瓜数量众多，任意两座城市之间都存在一条路径（否则傻瓜们会感到沮丧）。同时，任意两座城市之间至多只存在一条简单路径（否则傻瓜们会迷路）。

但这还不是贝尔兰特殊性质的全部。在这个国家，傻瓜有时会互相拜访，从而损坏道路。傻瓜们并不聪明，因此他们总是仅使用简单路径。

简单路径是指至多经过贝尔兰每座城市一次的路径。

贝尔兰政府已知傻瓜们所使用的路径。请帮助政府计算：对于每条道路，有多少个互不相同的傻瓜会经过它。

注意输入中傻瓜路径的给出方式。

The first line contains a single integer n (2 ≤ n ≤ 105) — 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 ≤ 105) — 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 2_i_ - 1 lives in city a__i and visits the fool number 2_i_, who lives in city b__i. The given pairs describe simple paths, because between every pair of cities there is only one simple path.

第一行包含一个整数 $n$（$2 \leq n \leq 10^5$）——城市的数量。

接下来的 $n-1$ 行，每行包含两个以空格分隔的整数 $u_i$、$v_i$（$1 \leq u_i, v_i \leq n$，且 $u_i \neq v_i$），表示城市 $u_i$ 与城市 $v_i$ 之间有一条道路相连。

下一行包含一个整数 $k$（$0 \leq k \leq 10^5$）——相互访问的“傻瓜”对的数量。

接下来的 $k$ 行，每行包含两个以空格分隔的数字。第 $i$ 行（$i > 0$）包含数字 $a_i$、$b_i$（$1 \leq a_i, b_i \leq n$）。这表示编号为 $2i-1$ 的傻瓜居住在城市 $a_i$，并前往拜访居住在城市 $b_i$ 的编号为 $2i$ 的傻瓜。所给的各对城市均对应一条简单路径，因为任意两座城市之间仅存在唯一一条简单路径。

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.

输出 $n-1$ 个整数，整数之间用空格分隔。第 $i$ 个数应等于能够通行第 $i$ 条道路的傻瓜数量。道路按其在输入中出现的顺序从 1 开始编号。

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.

在第一个样例中，傻瓜一号走第一条和第三条路，傻瓜三号走第二条、第一条和第四条路。

在第二个样例中，傻瓜一号、三号和五号走第一条路，傻瓜五号走第二条路，傻瓜三号走第三条路，傻瓜一号走第四条路。