You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 512.0 MB

Description

In the enchanted realm of Arborwyn, a colossal tree known as the Grand Arbor connected the kingdom’s villages through a vast network of magical paths. Each path, marked by weighted edges, represented the strength of the connections between settlements.

When a dark force threatened to sever these bonds, a brave council of leaders and warriors formed to protect their homeland. They realized they needed to determine the largest edge along any path between two villages, A and B, to prepare for the challenges ahead.

You will be given a tree with \(n\) node numbered 1 to \(n\) with weighted edge.
You will be asked \(q\) queries.
For each query you have to find the largest edge in path from \(A\) to \(B\).

Input

The first line contains two integers \(n\) and \(q\) (\(1 \le n, q \le 10^5\)). Each of the next \(n-1\) lines contains three integer \(u_i\), \(v_i\), \(w_i\), (\(1 \le u_i\), \(v_i \le n\) and \(1 \le w_i \le 10^5\)), meaning there is an edge between \(u_i\) and \(v_i\) with weight \(w_i\).

Each of the next \(q\) lines contains two integer \(A\), \(B\) (\(1 \le A, B \le n\) and \(A \ne B\)) describing the query.

Output

For each query. print the answer in a new line.

Sample

5 5
2 1 40
3 2 21
4 1 23
5 2 50
1 2
3 5
3 1
2 3
2 1

40
50
40
21
40