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

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 条边。