Taco Tree Maximum Weight Query

You are given a weighted tree with n nodes labeled from 1 to n. The tree is rooted at node 1. Each of the n-1 edges has an associated weight. You need to answer q queries. In each query, given two nodes a and b, find the maximum weight among all edges on the unique path connecting these two nodes.

The tree is provided in the following format:

• The first line contains two integers \(n\) and \(q\), where \(n\) is the number of nodes and \(q\) is the number of queries.
• The next \(n-1\) lines each contain three integers \(u\), \(v\), and \(w\), representing an edge between nodes \(u\) and \(v\) with weight \(w\).
• The following \(q\) lines each contain two integers \(a\) and \(b\), representing a query asking for the maximum edge weight on the path from node \(a\) to node \(b\).

Note: Use binary lifting and lowest common ancestor (LCA) techniques to efficiently answer the queries.

inputFormat

The input is read from stdin in the following format:

 
u1 v1 w1
u2 v2 w2
... (n-1 lines)
a1 b1
... (q lines)

Where:

• n is the number of nodes.
• q is the number of queries.
• Each of the next n-1 lines contains three integers u, v, and w, denoting an edge between nodes u and v with weight w.
• Each of the following q lines contains two integers a and b representing a query.

outputFormat

For each query, print the maximum weight found along the path connecting the given nodes. The answers for consecutive queries should be printed on separate lines to stdout.

## sample

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

7
4
7

</p>