$\tt{Pig}$ 获得一棵包含 $n$ 个顶点的树。他需要按顺序使用 $k$ 种不同颜色对树的边进行染色。 初始时所有边均为颜色 $\tt{0}$。第 $i$ 次染色时，$\tt{Pig}$ 会选取 $x_i$ 到 $y_i$ 的最短路径上的所有边，将其染为颜色 $i$（覆盖原有颜色）。请确定每条边的最终颜色。

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 10^6$，$1 \leq k \leq 10^6$） 接下来 $n-1$ 行每行两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示初始树结构 随后 $k$ 行每行两个整数 $\tt{x_i}$ 和 $\tt{y_i}$（$1 \leq x_i, y_i \leq n$），表示染色路径

按输入边的顺序输出每条边的最终颜色

对于样例$\tt{1}$ - 第一次染色（颜色 $1$）覆盖边 $1$（路径$1-2-3-4-5$）和边 $4$（路径$5-4$） - 第二次染色（颜色 $2$）覆盖边 $1$（路径$1-2$）、边 $\tt{3}$（路径$3-4$）、边 $5$（路径$5-6$） - 边 $2$（路径$2-3$）未被覆盖，保持颜色 $0$