Patrik 得到了一棵有 $n$ 个顶点的树。他决定用 $k$ 种不同的颜色给这棵树的边染色。
最初，树的所有边都被染成颜色 0。他将按从第 1 种到第 $k$ 种的顺序使用颜色，其中他会使用第 $i$ 种颜色将从 $x_i$ 号节点到 $y_i$ 号节点的最短路径上的所有边染上该颜色。如果路径上的一条边已经被染过色，新颜色将覆盖旧颜色。
请帮助 Patrik 确定每条边的最终颜色。
输入格式
输入的第一行包含数字 $n$ 和 $k$ ($2 \le n \le 10^6, 1 \le k \le 10^6$)，分别表示树的顶点数和颜色数。
接下来的 $n-1$ 行，每行包含数字 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。保证这些边构成一棵树。
接下来的 $k$ 行，每行包含数字 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le n$)，表示 Patrik 染色路径的起点和终点。
输出格式
在一行中，按照输入中给出的顺序打印每条边的最终颜色。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 15 | $u_i = i, v_i = i + 1$ 对于所有 $i$ |
| 2 | 15 | $n, k \le 2000$ |
| 3 | 45 | $n \le 10^5$ |
| 4 | 45 | 无附加限制 |
样例
输入 1
6 2 1 2 2 3 2 4 1 5 4 6 5 2 6 1
输出 1
2 0 2 1 2
输入 2
5 4 1 2 2 3 3 4 4 5 5 5 4 3 2 1 2 4
输出 2
3 4 4 0
输入 3
5 4 3 5 2 3 4 3 5 1 4 1 5 5 4 2 1 5
输出 3
1 3 3 4
说明
第一个样例的说明： 使用第一种颜色时，他染了第 1 条边和第 4 条边；然后使用第二种颜色时，他染了第 1 条、第 3 条和第 5 条边。