Maximum Edge Weight Query in a Tree

You are given a tree with N nodes. Each edge in the tree has an associated weight. The task is to answer Q queries. In each query, given two nodes u and v, you need to determine the maximum edge weight on the unique path between u and v.

The tree is provided in the form of edges, and it is guaranteed that there is exactly one path between any two nodes because of the tree structure. To solve this problem efficiently, you can use the binary lifting technique along with Lowest Common Ancestor (LCA) methods.

In mathematical terms, if the tree is represented by a set of nodes and weighted edges, for any two nodes u and v, you are required to compute:

$$ \max_{e \in P(u,v)} w(e) $$

where \(P(u,v)\) is the unique path between u and v, and \(w(e)\) is the weight of edge \(e\).

inputFormat

The input is given from stdin and has the following format:

N Q
u1 v1 w1
u2 v2 w2
...
u(N-1) v(N-1) w(N-1)
q1_u q1_v
q2_u q2_v
...
qQ_u qQ_v

Here, N denotes the number of nodes, Q is the number of queries, and the next N-1 lines describe the edges of the tree with two nodes and a weight for each edge. The subsequent Q lines contain two integers representing the nodes for each query.

outputFormat

For each query, output the maximum edge weight on the path between the two given nodes. Each result should be printed on a new line to stdout.

## sample

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

4
6
6

</p>