Heaviest Edge on Path

Given an undirected tree with n vertices and n-1 edges, where each edge has an associated weight, answer q queries. For each query, you are given two vertices u and v. Your task is to determine the weight of the heaviest edge along the unique path from u to v in the tree.

Formally, let \( n \) be the number of vertices and there are exactly \( n-1 \) edges. For each query \( (u, v) \), output the maximum weight among all edges encountered on the unique path between vertices \( u \) and \( v \).

This problem can be solved using a simple Depth First Search (DFS) for each query since the tree property ensures that there is exactly one path between any two vertices.

inputFormat

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

• The first line contains two integers \( n \) and \( q \), representing the number of vertices and the number of queries respectively.
• The next \( n-1 \) lines each contain three integers \( u \), \( v \), and \( w \), which describes an edge connecting vertex \( u \) and vertex \( v \) with weight \( w \).
• The following \( q \) lines each contain two integers \( u \) and \( v \), indicating a query where you need to find the heaviest edge on the path from \( u \) to \( v \).

outputFormat

For each query, output a single line containing the weight of the heaviest edge on the path from the first vertex to the second vertex.

## sample

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

6
5
6

</p>