도로 네트워크

N개의 도시와 도시들을 연결하는 N - 1개의 도로로 이루어진 도로 네트워크가 있다.

임의의 두 도시 사이에는 두 도시를 연결하는 경로가 정확히 하나 존재한다. 각 도로의 길이는 입력으로 주어진다.

K개의 도시 쌍이 주어진다. 각 쌍에 대해, 두 도시를 연결하는 경로 위에 있는 도로들 중 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하라.

첫째 줄에 N (2 <= N <= 100,000)이 주어진다.

다음 N - 1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. 이는 도시 A와 도시 B 사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000 이하의 양의 정수이다.

다음 줄에 K (1 <= K <= 100,000)가 주어진다.

다음 K개 줄에는 서로 다른 두 자연수 D와 E가 주어진다. 각 쌍에 대해 D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력해야 한다.

총 K개 줄을 출력한다. 각 줄에는 해당 질의의 두 도시 D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력한다.