Description

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.

Input Format

In the first line of input, there are numbers $n$ and $k$ ($2 ≤ n ≤ 10^6, 1 ≤ k ≤ 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 ≤ u_i, v_i ≤ 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 ≤ x_i, y_i ≤ n$), representing the nodes between which Patrik paints the edges.

Output Format

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 1

2 0 2 1 2

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

3 4 4 0

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

1 3 3 4

Hint

Clarification 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$.

Scoring