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
| Sample Input | Sample Output |
|---|---|
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 |
Notes
Dataset is huge. Use faster I/O methods.