DISQUERY  Distance Query
English  Vietnamese 
The traffic network in a country consists of N cities (labeled with integers from 1 to N) and N1 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 N1 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
udit_003:
20170410 22:53:30
AC in one go!! good problem must try Last edit: 20170410 22:54:24 

hamzaziadeh:
20160918 23:24:08
So ez! AC in 1 go, good problem for noobs.. 

shas19:
20160716 01:08:01
worked with HLD (even though it is an overkill) 

Luis Manuel Díaz Barón:
20150423 17:08:02
It's true [20][100005] => ACCEPTED, [20][100005] => TLE


Mohammadreza Osouli:
20141128 14:54:54
runtime error !!


Ghost Of Perdition:
20130524 01:00:18
very strict time limit .... why??


darryl:
20111128 11:40:45
Is HLdecomposition + sparse table enough?


刘启鹏:
20100105 12:38:19
remember [20][110000]==>AC [110000][20]==>TLE 

Tony Beta Lambda:
20090622 10:59:01
An O(nlogn) algorithm is needed instead of the O(n(logn)^2) one against the new test data. 

~!(*(@*!@^&:
20090620 23:20:14
Add full test and rejudge. 
Added by:  ~!(*(@*!@^& 
Date:  20090228 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COI 06 