Under construction

Still being built. Things may change

Road Network

Time limit1sMemory limit256 MB

Summary
For a tree with weighted edges, answer many queries asking for the minimum and maximum edge weight on the path between two given nodes.
Level

Medium6 of 10

Topics
Tree, Binary search, Graph
Solved
No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

  1. Example 1

    Input
    5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2
    Expected output
    100 200
50 150
50 100

  2. Example 2

    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
    Expected output
    2 6
1 4
6 6
2 2
2 6

  3. Example 3

    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
    Expected output
    1 2
2 4
1 5
2 2
1 4