레이팅 미적용Patrik received a tree with \(n\) vertices. He decided to paint the edges of that tree
using \(k\) different colors.
Initially, all edges of the tree are painted with color 0. He will use the colors in
order from the first to the \(k\)-th, where he will use the \(i\)-th color to paint all the
edges on the shortest path from the \(x_{i}-th\) to the \(y_{i}-th\) node. If an edge on that
path is already painted, the new color will overwrite the old one.
Help Patrik determine the final color of each edge.
Subtask 1 (15 points): \(u_{i} = i\), \(v_{i} = i + 1\) za svaki \(i\)
Subtask 2 (15 points): n, \(k \le 2000\)
Subtask 3 (45 points): \(n \le 10^{5}\)
Subtask 4 (45 points): No additional constraints.
In the first line of input, there are numbers \(n\) and \(k\) (\(2 \le n \le 10^{6}\), \(1 \le k \le 10^{6}\)), representing the number
of vertices in the tree and the number of colors.
In the next \(n - 1\) lines, there are numbers \(u_{i}\) and \(v_{i}\) (\(1 \le u_{i}\), \(v_{i} \le n\)) — the \(i\)-th edge connects the vertices
\(u_{i}\) and \(v_{i}\). It is guaranteed that the edges form a tree.
In the following \(k\) lines, there are numbers \(x_{i}\) and \(y_{i}\) (\(1 \le x_{i}\), \(y_{i} \le n\)), representing the nodes between
which Patrik paints the edges.
In a single line, print the final color of each edge in the order they were given in the input.
6 2
1 2
2 3
2 4
1 5
4 6
5 2
6 12 0 2 1 25 4
1 2
2 3
3 4
4 5
5 5
4 3
2 1
2 43 4 4 05 4
3 5
2 3
4 3
5 1
4 1
5 5
4 2
1 51 3 3 4Clarification of the first example:
With the first color, he painted edges 1 and 4, and then with the second color, he painted edges 1, 3, and
5.