Problem ID:
lubenica
Points:
2.5 (partial)
Time limit:
3.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Perl, Python
Cho một cây ~N~ đỉnh, ~N-1~ cạnh, cạnh có trọng số. ~K~ truy vấn, mỗi truy vấn in ra ~2~ số nguyên là trọng số cạnh bé nhất và lớn nhất trên đường đi từ đỉnh ~D~ đến đỉnh ~E~.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên ~N~, ~2 \leq N \leq 100000~.
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ạnh (~A,B~) có trọng số ~C~. ~C~ là số nguyên dương không vượt quá ~1000000~.
Dòng tiếp theo chứa số nguyên ~K~, ~1 \leq K \leq 100000~.
Mỗi dòng trong số ~K~ dòng tiếp theo chứa ~2~ số nguyên phân biệt ~D~ và ~E~.
Kết quả ra
Mỗi dòng trong số ~K~ dòng chứa ~2~ số nguyên - trọng số cạnh bé nhất và lớn nhất trên đường đi từ đỉnh ~D~ đến đỉnh ~E~ tương ứng.
Sample 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
Sample Output
2 6
1 4
6 6
2 2
2 6
Nguồn: COCI 2006
Comments