Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Graph Stuff !!!

By CLown1331 · Limits 1s, 512 MB

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 <= n, q <= 105 ). Each of the next n-1 lines contains three integer ui, vi, wi, ( 1 <= ui , vi <= n and
1 <= wi <= 105
), meaning there is an edge between ui and vi with weight wi.

Each of the next q lines contains two integer A, B ( 1 <= A, B <= n and A != B ) describing the query.

Constraints

1 <= n, q <= 105

1 <= ui , vi <= n and
1 <= wi <= 105

1 <= A, B <= n and A != B

Output

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

Samples

InputOutput
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
InputOutput
5 5
2 1 2
3 2 31
4 1 2
5 2 5
1 4
1 5
3 1
2 3
2 1
2
5
31
31
2


Consider the first case,

In query 1, from 1 to 2, there is only one edge and so the answer is 40.

In query 2, from 3 to 5, largest edge in path is 2 -- 5 with weight 50, so the answer is 50.

Discussion

Statistics


90% Solution Ratio

skmonirEarliest, Feb '18

Tarik.amtolyFastest, 71778.0s

Tarik.amtolyLightest, 10 MB

sakibalaminShortest, 2324B

Submit

Login to submit