他们说伯兰德有两个问题,傻瓜和道路。此外,贝尔兰有n座城市,居住着傻瓜,并有道路相连。 Berland 的所有道路都是双向的。由于贝尔兰德有很多傻瓜,所以每对城市之间都有一条路径(否则傻瓜会不高兴)。而且,每对城市之间只有一条简单的路径(否则傻瓜们就会迷路)。
但这并不是 Berland 特色的结束。在这个国家,傻瓜有时会互相拜访,从而破坏道路。傻瓜不太聪明,所以他们总是只使用简单的路径。
简单路径是经过每个 Berland 城市不超过一次的路径。
Berland政府知道傻瓜们走的路。帮助政府计算每条路,有多少个不同的傻瓜可以走在上面。
注意输入中如何给出傻瓜路径。
输入
第一行包含一个整数 n (2 ≤ n ≤ 105) — 城市数量。
接下来的 n - 1 行每行包含两个空格分隔的整数 ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi),这意味着有一条道路连接城市 ui 和 vi。
下一行包含整数 k (0 ≤ k ≤ 105) — 互相拜访的傻瓜对的数量。
接下来的 k 行包含两个空格分隔的数字。第 i 行 (i > 0) 包含数字 ai, bi (1 ≤ ai, bi ≤ n)。这意味着住在ai城市的傻瓜2i - 1拜访了住在bi城市的傻瓜2i。给定的对描述了简单路径,因为每对城市之间只有一条简单路径。
输出
打印 n - 1 个整数。整数应该用空格分隔。第 i 个数字应该等于可以走第 i 条路的傻瓜数量。道路按照它们在输入中出现的顺序从 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
注意
在第一个样本中,傻瓜 1 号走第一条和第三条路,傻瓜 3 号走第二条、第一条和第四条路。
在第二个样本中,傻瓜 1、3 和 5 号走第一条路,傻瓜 5 号走第二条路,傻瓜 3 号走第三条路,傻瓜 1 号走第四条路。