小象非常爱树,特别喜欢根树。
他有一棵由 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