Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LUBENICA - Lubenica

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/lubenica


{if $par==""} {assign var=par value=$locale} {/if}
{if $par=="vn"} {literal}

Mạng lưới giao thông ở 1 nước bao gồm N thành phố (đánh số từ 1 đến N) và N-1 đường nối các thành phố với nhau. Có một đường đi duy nhất giữa mỗi cặp thành phố. Mỗi con đường có một độ dài xác định.

Viết chương trình, với mỗi K cặp thành phố cho trước, tìm độ dài của con đường ngắn nhất và dài nhất trên đường đi giữa 2 thành phố này.

Dữ liệu

Dòng đầu tiên chứa số nguyên N, 2 ≤ N ≤ 100 000.

Mỗi dòng trong số N-1 dòng tiếp theo chứa 3 số nguyên A, B, C cho biết có một con đường độ dài C giữa thành phố A và thành phố B. Độ dài của mỗi con đường là số nguyên dương không vượt quá 1000000.

Dòng tiếp theo chứa số nguyên K, 1 ≤ K ≤ 100 000.

Mỗi dòng trong số K dòng tiếp theo chứa 2 số nguyên D và E - chỉ số của 2 thành phố cần truy vấn.

Kết qủa

Mỗi dòng trong số K dòng chứa 2 số nguyên - độ dài của con đường ngắn nhất và dài nhất trên đường nối giữa 2 thành phố tương ứng.

Ví dụ

Dữ liệu:
5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2
Kết qủa
100 200
50 150
50 100

Dữ liệu:
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

Kết qủa
2 6
1 4
6 6
2 2
2 6

Dữ liệu:
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

Kết qủa
1 2
2 4
1 5
2 2
1 4
{/literal}{elseif ($par=="en" || $par=="")}{literal}

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
{/literal} {/if}

Được gửi lên bởi:Jimmy
Ngày:2007-12-18
Thời gian chạy:1.210s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Croatian OI 2006

hide comments
2016-06-30 04:24:08
Để cài bài này em mất hết 1 đêm thêm 2 tiếng buổi sáng các bác ạ :3
2016-02-03 10:46:20
THAM KHAO: Codevnspoj.blogspot.com
2015-06-18 17:52:22 there's no salvation for me...
nhân danh sự tinh tế, đừng quên xoá tên file :v
2015-06-18 17:09:48 even when you try to hurt me...
á đù sao 0 :(((
2015-01-02 08:09:13 Sơn Tùng M-TP
k dùng LCA có được 40 đ :)
2015-01-02 07:10:18 Sơn Tùng M-TP
xây cây xem. :v
2015-01-02 07:08:08 Sơn Tùng M-TP
2 lần DFS à.
2014-12-30 14:33:06 Lollipop
90 la bi gi nhi
2014-12-04 15:38:40 [$Zeus$]
Code dài và phê :v học LCA làm bài này thật bổ ích
2014-11-25 04:44:43 Prismatic
ảo :)) lần đầu nộp dc 90, lần sau nộp lại code cũ dc 100 :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.