Road Network

There is a road network with N cities and N - 1 roads connecting them.

For every pair of cities, there is exactly one path connecting the two cities. The length of each road is given in the input.

You are given K pairs of cities. For each pair, find the length of the shortest road and the length of the longest road on the path connecting the two cities.

The first line contains N (2 <= N <= 100,000).

Each of the next N - 1 lines contains three integers A, B, and C, meaning that there is a road of length C between cities A and B. Every road length is a positive integer not greater than 1,000,000.

The next line contains K (1 <= K <= 100,000).

Each of the next K lines contains two distinct positive integers D and E. For each pair, output the shortest and longest road lengths on the path connecting D and E.

Print K lines. For each query, print the length of the shortest road and the length of the longest road on the path connecting D and E.