题目描述

在一片神秘的森林中，有 $n$ 个古老的树屋，由 $n-1$ 条蜿蜒的小径连接。这些小径构成了一棵树，确保任意两个树屋之间都有一条唯一的路径。

森林中的信使们负责在各个树屋之间传递消息。每次传递消息时，他们会选择两个树屋 $(u, v)$，然后沿着从 $u$ 到 $v$ 的唯一路径行走。每经过一条小径，他们就会在这条小径上留下一个标记，表示这条小径被使用了一次。

现在，你已经知道了 $k$ 次消息传递的起点和终点。你的任务是计算每条小径上有多少个标记。

输入格式

第一行包含两个整数 $n$（$2 \leq n \leq 10^5$），$k$（$1 \leq k \leq 10^5$）分别表示树屋的数量和消息传递的次数。

接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示第 $i$ 条小径连接的树屋 $u_i$ 和 $v_i$。

接下来 $k$ 行，每行包含两个整数 $a_j$ 和 $b_j$（$1 \leq a_j, b_j \leq n$），表示第 $j$ 次消息传递的起点和终点。

输出格式

输出 $n-1$ 个整数，表示每条小径上的标记数量。输出的顺序应与输入中小径的顺序一致。

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

1 1 1 2

样例解释

第一条小径（$1-2$）被消息传递（$3-5$）经过一次。

第二条小径（$1-3$）被消息传递（$3-5$）经过一次。

第三条小径（$2-4$）被消息传递（$4-5$）经过一次。

第四条小径（$2-5$）被消息传递（$4-5$）和（$3-5$）各经过一次，总共两次。

数据范围与提示

• 对于 $100\%$ 的数据，$2 \leq n \leq 10^5$，$1 \leq k \leq 10^5$。