DISQUERY - Distance Query


The traffic network in a country consists of N cities (labeled with integers from 1 to N) and N-1 roads connecting the cities. There is a unique path between each pair of different cities, and we know the exact length of each road.

Write a program that will, for each of the K given pairs of cities, find the length of the shortest and the length of the longest road on the path between the two cities.

Input

The first line of input contains an integer N, 2 ≤ N ≤ 100 000. Each of the following N-1 lines contains three integers A, B and C meaning that there is a road of length C between city A and city B.

The length of each road will be a positive integer less than or equal to 1 000 000.
The next line contains an integer K, 1 ≤ K ≤ 100 000. Each of the following K lines contains two different integers D and E – the labels of the two cities constituting one query.

Output

Each of the K lines of output should contain two integers – the lengths from the task description for the corresponding pair of the cities.

Sample

Input:
5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2

Output:
100 200
50 150
50 100
Input:
7
3 6 4
1 7 1
1 3 2
1 2 6
2 5 4
2 4 4
5
6 4
7 6
1 2
1 3
3 5

Output:
2 6
1 4
6 6
2 2
2 6

hide comments
sadat999: 2022-05-13 14:12:45

Can anybody please tell what issues there are with test case 9 or 10?

deardiwakar: 2021-12-17 20:50:25

@samarth5611, I am facing the same issue, how did you resolve it?

cjn2007: 2021-12-16 13:28:56

AC in one go!

changyouren: 2021-09-30 11:04:32

use persistent segment tree + LCA
your algorithm should O(nlgn) not O(nlgn*lgn)

samarth5611: 2021-09-07 13:45:52

I am getting Wrong answer on test Case 10,
could someone tell me test case

nikhil0010: 2021-07-13 20:26:50

solve codeforces 609E after this problem :)

aldgebu: 2021-03-22 16:47:25

I just print "answer" and I got 10 tests AC. have this task checker or something like that ? Whata fuck re you doin ?

[NG]: You haven't got anything AC. You do realize anyone can view your submission history, don't you?

Last edit: 2021-03-22 23:44:56
pinku7499: 2020-06-23 10:21:12

How simple...!

shawnliang: 2019-12-21 09:49:58

AC in 2s.why?

abhimanyu_1998: 2019-02-20 20:35:42

binary lifting should do the job


Added by:psetter
Date:2009-02-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 06