Maximum Difficulty Path in a Kingdom

In a kingdom there are n castles connected by m bidirectional roads. Each road has an associated difficulty level. The kingdom is structured in such a way that the castles are connected and form a tree. For each query, you are given two castles and you need to determine the difficulty of the most challenging road along the unique simple path connecting them. In other words, for each query you must find the maximum edge weight on the path between the two given castles.

The input guarantees that there is exactly one simple path between any two castles.

Mathematically, let the path between castles \(a\) and \(b\) be defined as a sequence of edges whose difficulties are \(d_1, d_2, \dots, d_k\). You are required to output \(\max_{1 \leq i \leq k} d_i\) for each query.

inputFormat

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

n m
u1 v1 d1
u2 v2 d2
... (m lines in total)
q
a1 b1
a2 b2
... (q lines in total)

Where:

• n: Number of castles.
• m: Number of roads.
• Each of the next m lines contains three integers: two castles u and v connected by a road and the difficulty d for that road.
• q: Number of queries.
• Each of the next q lines contains two integers a and b, representing a query asking for the maximum difficulty on the path from castle a to castle b.

outputFormat

For each query, output a single line containing one integer—the maximum difficulty encountered along the path connecting the two castles. The result for each query should be printed on a new line to stdout.

## sample

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

6
5

</p>