Maximum Toll on Unique Paths

You are given a tree representing a network of cities connected by roads. Each road has an associated toll fee. Since the tree is connected, there is exactly one unique path between any two cities.

Your task is to answer several queries. For each query, you must determine the maximum toll fee found along the unique path between two given cities.

To solve this problem efficiently, you might want to use techniques such as binary lifting to compute the lowest common ancestor (LCA) and track the maximum edge weight along the path. The maximum toll between two cities u and v can be defined as: $$ \text{maxToll}(u,v)=\max_{e \in P(u,v)}(\text{toll fee of } e) $$ where P(u, v) denotes the set of roads on the unique path from u to v.

inputFormat

The input is given via stdin in the following format:

• The first line contains an integer n representing the number of cities.
• The next n - 1 lines each contain three integers u v w, representing a road between cities u and v with a toll fee of w.
• The next line contains an integer q representing the number of queries.
• Each of the following q lines contains two integers u v, representing a query to determine the maximum toll fee on the unique path between city u and city v.

It is guaranteed that the given roads form a tree (i.e. a connected graph with no cycles).

outputFormat

For each query, output a single line via stdout containing one integer – the maximum toll fee on the unique path between the two specified cities.

## sample

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

6

</p>