No testdata at current.

时间限制： 3.0 秒

空间限制： 512 MB

题目描述

Coco 家门有一棵 $n$ 个节点的苹果树，这棵苹果树的结构可以抽象成一棵以 $1$ 号节点为根的树，树上的每个节点都挂着一个苹果蓝。

最开始，所有苹果篮都是空的。接下来，Coco 会进行 $m$ 次操作。第 $i$ 次操作，她会选择两个节点 $a_i$ 和 $b_i$，并执行如下操作：

• 对于所有在 $a_i$ 子树中或在 $b_i$ 子树中的节点，给它们的苹果篮中均放入第 $i$ 种颜色的苹果。

在所有操作结束后，Coco 想知道对于每一个节点 $i$，有多少个节点 $j$（包括节点 $i$ 自己），满足节点 $i$ 和节点 $j$ 的苹果篮中至少有一个相同颜色的苹果？

输入格式

从标准输入读入数据。

第一行，输入两个整数 $n$ 和 $m$。

接下来 $n-1$ 行，每行输入两个整数 $x,y$，表示苹果树的一条边。

接下来 $m$ 行，第 $i$ 行输入两个整数 $a_i$ 和 $b_i$，表示一次操作。

输出格式

输出到标准输出。

输出共一行，包含 $n$ 个整数，第 $i$ 个整数表示与第 $i$ 个节点的苹果篮有相同颜色苹果的节点数。

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

0 0 3 3 3

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

0 3 6 5 3 8 7 7 7 7

子任务

对于所有数据，$2\le n\le 10^5,\ 1\le m\le 10^5$。