← 返回题目列表

Codeforces · 191/C

C. 傻瓜与道路

中文机器翻译题面 查看原题

他们说伯兰德有两个问题,傻瓜和道路。此外,贝尔兰有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 号走第四条路。