Problem hidden
LUBENICA - Lubenica
English | Vietnamese |
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.
Example
Input 1 6 5 100 25 50 50 10 20 23 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 |
Input 9 1 2 2 2 3 1 3 4 5 2 7 4 1 5 3 5 6 1 5 9 2 1 8 3 5 6 9 7 8 9 4 1 2 7 3 Output 1 2 2 4 1 5 2 2 1 4 |
Added by: | Duc |
Date: | 2007-12-18 |
Time limit: | 1.210s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Croatian OI 2006 |