시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1434 568 383 41.316%

문제

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를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력한다.

예제 입력 1

5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2

예제 출력 1

100 200
50 150
50 100
W3sicHJvYmxlbV9pZCI6IjMxNzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWI4NWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5OXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YzY0MCBcdWFkZjggXHViM2M0XHVjMmRjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBOLTFcdWFjMWNcdWM3NTggXHViM2M0XHViODVjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWIzYzRcdWI4NWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHVhYzAwIFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMzMGRcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjNzIwXHVjNzdjXHVkNTVjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2QxZCBLXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkYyBcdWMzMGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWI0NTAgXHViM2M0XHVjMmRjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWMgXHVjMGMxXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YzY0MCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTi0xXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzEzOCBcdWM4MTVcdWMyMTggQSwgQiwgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIEFcdWM2NDAgQlx1YzBhY1x1Yzc3NFx1YzVkMCBcdWFlMzhcdWM3NzRcdWFjMDAgQ1x1Yzc3OCBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjNzg4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxLDAwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEsgJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgS1x1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHVjNzkwXHVjNWYwXHVjMjE4IERcdWM2NDAgRVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIERcdWM2NDAgRVx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YzY0MCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTc0XHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDFkIEtcdWFjMWMgXHVjOTA0XHVjNWQwJm5ic3A7RFx1YzY0MCBFXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE3NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Imx1YmVuaWNhIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgdHJhZmZpYyBuZXR3b3JrIGluIGEgY291bnRyeSBjb25zaXN0cyBvZiBOIGNpdGllcyAobGFiZWxlZCB3aXRoIGludGVnZXJzIGZyb20gMSB0byBOKSBhbmQgTi0xIHJvYWRzIGNvbm5lY3RpbmcgdGhlIGNpdGllcy4gVGhlcmUgaXMgYSB1bmlxdWUgcGF0aCBiZXR3ZWVuIGVhY2ggcGFpciBvZiBkaWZmZXJlbnQgY2l0aWVzLCBhbmQgd2Uga25vdyB0aGUgZXhhY3QgbGVuZ3RoIG9mIGVhY2ggcm9hZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCwgZm9yIGVhY2ggb2YgdGhlIEsgZ2l2ZW4gcGFpcnMgb2YgY2l0aWVzLCBmaW5kIHRoZSBsZW5ndGggb2YgdGhlIHNob3J0ZXN0IGFuZCB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHJvYWQgb24gdGhlIHBhdGggYmV0d2VlbiB0aGUgdHdvIGNpdGllcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgTiwgMiAmbGU7IE4gJmxlOyAxMDAgMDAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTi0xIGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIEEsIEIgYW5kIEMgbWVhbmluZyB0aGF0IHRoZXJlIGlzIGEgcm9hZCBvZiBsZW5ndGggQyBiZXR3ZWVuIGNpdHkgQSBhbmQgY2l0eSBCLiBUaGUgbGVuZ3RoIG9mIGVhY2ggcm9hZCB3aWxsIGJlIGEgcG9zaXRpdmUgaW50ZWdlciBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMSAwMDAgMDAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgSywgMSAmbGU7IEsgJmxlOyAxMDAgMDAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgSyBsaW5lcyBjb250YWlucyB0d28gZGlmZmVyZW50IGludGVnZXJzIEQgYW5kIEUgJm5kYXNoOyB0aGUgbGFiZWxzIG9mIHRoZSB0d28gY2l0aWVzIGNvbnN0aXR1dGluZyBvbmUgcXVlcnkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+RWFjaCBvZiB0aGUgSyBsaW5lcyBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdHdvIGludGVnZXJzICZuZGFzaDsgdGhlIGxlbmd0aHMgZnJvbSB0aGUgdGFzayBkZXNjcmlwdGlvbiBmb3IgdGhlIGNvcnJlc3BvbmRpbmcgcGFpciBvZiB0aGUgY2l0aWVzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==