Path Edge Update on Tree

You are given a tree with n nodes and n-1 edges. Initially, the weight of every edge is \(0\). You are also given q operations. In the i-th operation, you are given two nodes \(u\) and \(v\), and you must set (overwrite) the weight of every edge on the unique simple path between \(u\) and \(v\) to \(i\). After processing all operations, output the final weight of each edge in the same order as the input.

Note: The path is defined as the unique simple path between the two nodes in the tree.

inputFormat

The first line contains two integers \(n\) and \(q\) -- the number of nodes and the number of operations.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), representing an edge between nodes \(u\) and \(v\).

The following \(q\) lines each contain two integers \(u\) and \(v\) representing an operation: update all edges on the path from \(u\) to \(v\) to the current operation index (starting from 1).

outputFormat

Output \(n-1\) integers separated by spaces, where the \(i\)-th integer is the final weight of the \(i\)-th edge (in the same order as the input).

sample

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

3 3 1 3