stablo (COCI CONTEST_#5)
Time limit: 3.5 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: tree decomposition, segment tree, lowest common ancestor, tree

Task Stablo II
3.5 seconds / 512 MiB / 120 points

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 *xi*-th to the *yi*-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

In the first line of input, there are numbers *n* and *k* (2 ≤ *n* ≤ 10⁶, 1 ≤ *k* ≤ 10⁶), representing the number of vertices in the tree and the number of colors.

In the next *n* − 1 lines, there are numbers *ui* and *vi* (1 ≤ *ui, vi* ≤ *n*) — the *i*-th edge connects the vertices *ui* and *vi*. It is guaranteed that the edges form a tree.

In the following *k* lines, there are numbers *xi* and *yi* (1 ≤ *xi, yi* ≤ *n*), representing the nodes between which Patrik paints the edges.

#### Output

In a single line, print the final color of each edge in the order they were given in the input.

##### Scoring

| Subtask | Points | Constraints                       |
|---------|--------|-----------------------------------|
| 1       | 15     | $u_i = i, v_i = i + 1$ za svaki i |
| 2       | 15     | $n, k \le 2000$                   |
| 3       | 45     | $n \le 10^5$                      |
| 4       | 45     | No additional constraints.        |

![](_page_0_Picture_16.jpeg)

![](_page_0_Picture_18.jpeg)

##### Examples

| input     | input   | input   |
|-----------|---------|---------|
| 6 2       | 5 4     | 5 4     |
| 1 2       | 1 2     | 3 5     |
| 2 3       | 2 3     | 2 3     |
| 2 4       | 3 4     | 4 3     |
| 1 5       | 4 5     | 5 1     |
| 4 6       | 5 5     | 4 1     |
| 5 2       | 4 3     | 5 5     |
| 6 1       | 2 1     | 4 2     |
|           | 2 4     | 1 5     |
| output    | output  | output  |
| 2 0 2 1 2 | 3 4 4 0 | 1 3 3 4 |

![](_page_1_Picture_0.jpeg)

##### 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.

Starter code:

Grader code:

Setup script:

Evaluation script: