题目描述

《题意》

【Fools and Roads】 伯兰有 n 座城市，住着傻瓜，由道路连接。伯兰的所有道路都是双向的。由于伯兰有很多傻瓜，每对城市之间都有一条路径（否则傻瓜们会不高兴）。 而且，每对城市之间最多只有一条简单路径（否则傻瓜们会迷路）。 但这还不是伯兰的全部特色。在这个国家，傻瓜们有时会互相串门，从而破坏道路。傻瓜们不太聪明，所以他们总是只使用简单路径。 简单路径是指：经过每个伯兰城市不超过一次的路径。 伯兰政府知道傻瓜们使用的路径。请帮助政府统计每条道路，有多少个不同的傻瓜会经过它。

输入格式

第一行一个整数 n （2≤n≤10^5 ）。 接下来 n-1 行，每行两个正整数 x,y （1≤x,y≤n,x!=y ），表示 x 与 y 城市之间有一条路。 接下来一个整数 k （0≤k≤10^5）。 接下来 k 行，每行两个正整数 x,y （1≤x,y≤n ），表示有一个傻瓜从 x城 旅行到 y城 。

输出格式

一行空格分隔的 n-1 个整数，按输入顺序输出每一条路被走过的次数。路的编号按输入顺序从1开始。

样例

输入样例 1

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

输出样例 1

2 1 1 1

输入样例 2

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

输出样例 2

3 1 1 1

输入样例 3

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

输出样例 3

2 3 2

输入样例 4

3
1 2
2 3
0

输出样例 4

0 0