← 返回题目列表

Codeforces · 258/E

E. 小象和树

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

小象非常爱树,特别喜欢根树。

他有一棵由 n 个节点组成的树(节点编号从 1 到 n),根位于节点号 1。树的每个节点都包含一些数字列表,这些数字列表最初为空。

小象想要应用 m 次运算。在第 i 次操作 (1 ≤ i ≤ m) 中,他首先将编号 i 添加到根位于节点编号 ai 的子树的所有节点的列表中,然后将编号 i 添加到根位于节点 bi 的子树的所有节点的列表中。

应用所有操作后,小象想要对每个节点 i 进行计数 ci — 整数 j (1 ≤ j ≤ n; j ≠ i) 的数量,使得第 i 个和第 j 个节点的列表至少包含一个公共数字。

帮助小象,为他数数 ci。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 105) — 树节点的数量和操作的数量。

以下 n - 1 行中的每一行都包含两个空格分隔的整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi),这意味着节点 ui 和 vi 之间有一条边。

接下来的 m 行包含两个空格分隔的整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi),代表第 i 次操作中节点的索引。

保证给定的图是无向树。

输出

在一行中打印 n 个空格分隔的整数 — c1, c2, ..., cn。

示例

输入 #1

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

输出 #1

0 3 3 3 3

输入 #2

11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8

输出 #2

0 6 7 6 0 2 0 5 4 5 5