Optimal Heavy-Light Decomposition

In this problem, you are given a rooted tree (with root 1) and a series of queries. For each query, you need to determine the number of segments (chains) that are accessed on the unique path between two nodes when using a heavy‐light decomposition.

In heavy‐light decomposition the tree edges are partitioned into heavy edges and light edges. An edge between a node and its heavy child (the unique one on the heavy chain) is considered heavy and can have an arbitrary length, while all light edges have length 1. Note that different decompositions may yield different chain counts for the same queries.

Your task is to output a valid heavy‐light decomposition scheme such that when processing all the queries, the total number of chains accessed is as small as possible. In other words, if your decomposition results in a total query chain count x and the standard (optimal) answer has chain count x₀, the scoring is determined by a parameter \[ a=\left\lfloor\frac{q}{300}\right\rfloor \] and the score is awarded as follows:

• 10 points, if \( x \le x_0 \).
• 8 points, if \(0 < (x - x_0) \le a\).
• 7 points, if \(a < (x - x_0) \le 2a\).
• 6 points, if \(2a < (x - x_0) \le 3a\).
• 1 point, if a legal scheme is output.

We provide the executable Div_Checker.exe to verify your answer. Place it in the same folder as your program along with div.in (the input file) and div.out (your program's output file). When you run it, if your output is valid, it will print:

Your answer is XXX.

Note: Do not use file input/output in your final submission. Use standard input and output instead.

inputFormat

The first line contains two integers n and q, representing the number of nodes in the tree and the number of queries, respectively.

The next n-1 lines each contain two integers u and v indicating an edge between nodes u and v. The tree is rooted at node 1.

The following q lines each contain two integers u and v representing a query that asks for the number of heavy/light chains accessed on the unique path between nodes u and v.

outputFormat

Output a single integer, which is the sum over all queries of the number of chains accessed on the path between the queried nodes based on your heavy-light decomposition scheme.

sample

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

7