Regular Meeting

Time limit2sMemory limit512 MB

Summary

Given a weighted tree, for each query range of vertices S to E, find the meeting vertex that minimizes the largest bottleneck distance to the people in that range.

Level: Medium7 of 10
Topics: Tree, Union-find, Segment tree
Solved: No attempts yet

Problem

A tree with $N$ vertices is given. Each vertex is numbered from 1 to $N$ in order. The $i$ -th edge connects vertex $A_i$ and vertex $B_i$ , and its weight is $C_i$ ( $1 \le i < N$ ).

The distance between two vertices in the tree is defined as the maximum edge weight on the shortest path connecting them. The distance between the same two vertices is defined as 0.

People living in the tree plan to hold $Q$ meetings. The $i$ -th meeting is attended by people living at vertices numbered from $S_i$ to $E_i$ , inclusive. Each meeting takes place at some vertex $v$ in the tree. Choose $v$ so that the maximum distance from $v$ to any attendee is as small as possible.

Write a program that finds this minimum value.

Input

The first line contains two integers $N$ and $Q$ , separated by a space. The next $N-1$ lines describe the edges. Line $i+1$ contains three integers $A_i$ , $B_i$ , and $C_i$ , separated by spaces, which means there is an edge of weight $C_i$ between vertex $A_i$ and vertex $B_i$ .

The next $Q$ lines describe the meetings. Line $N+i$ contains two integers $S_i$ and $E_i$ , separated by a space, which describe the $i$ -th meeting.

Output

Print $Q$ lines. The $i$ -th line contains the answer for the $i$ -th meeting.

Limits

$1 \le N \le 300,000$
$1 \le Q \le 300,000$
$1 \le A_i \le N$ ( $1 \le i < N$ )
$1 \le B_i \le N$ ( $1 \le i < N$ )
$A_i \ne B_i$ ( $1 \le i < N$ )
$1 \le C_i \le 10^9$ ( $1 \le i < N$ )
$1 \le S_i \le E_i \le N$ ( $1 \le i \le Q$ )

Examples1

Example 1
Input
```
3 3
1 2 1
2 3 2
1 2
2 3
1 3
```
Expected output
```
1
2
2
```