Server Time: Sun Oct 20, 2019 12:48 am
Welcome ( logout
1162 - Min Max Roads
  PDF (English) Statistics Forum
Time Limit: 3 second(s) Memory Limit: 64 MB

You live in a Big country where there are many bi-directional roads connecting the cities. Since the people of the country are quite intelligent, they designed the country such that there is exactly one path to go from one city to another. A path consists of one or more connected roads.

Here cities are denoted by integers and each road has a cost of traveling. Now you are given the information about the Country. And you are given some queries, each consists of two cities. You have to find the shortest and longest road in the path from one city to another.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

The first line of each case is a blank line. The next line contains n (2 ≤ n ≤ 105) denoting the number of cities. Then there will be n-1 lines containing three integers each. They will be given in the form u v w (1 ≤ u, v ≤ n, 0 < w ≤ 105, u ≠ v) meaning that there is a road between u and v and the cost of the road is w.

The next line contains an integer q (1 ≤ q ≤ 25000) denoting the number of queries. Each of the next q lines contains two integers x and y (1 ≤ x, y ≤ n, x ≠ y).

Output

For each case, print the case number in a single line. Then for each query x y, you should print one line containing the shortest and longest road along the path. See the samples for formatting.

Sample Input

Output for Sample Input

2

 

6

3 6 50

2 5 30

2 4 300

1 2 100

1 3 200

4

1 4

4 6

2 5

3 5

 

2

1 2 100

1

1 2

Case 1:

100 300

50 300

30 30

30 200

Case 2:

100 100

Note

Dataset is huge. Use faster i/o methods.


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan