시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1899 711 471 39.747%

문제

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+XHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMzMGRcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjNzIwXHVjNzdjXHVkNTVjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2QxZCBLXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkYyBcdWMzMGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1YyBcdWMwYzFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOLTFcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBBLCBCLCBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gQVx1YzY0MCBCXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWUzOFx1Yzc3NFx1YWMwMCBDXHVjNzc4IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDEsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgSyAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBLXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWM3OTBcdWM1ZjBcdWMyMTggRFx1YzY0MCBFXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gRFx1YzY0MCBFXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NzRcdWMxMWMgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkMWQgS1x1YWMxYyBcdWM5MDRcdWM1ZDAmbmJzcDtEXHVjNjQwIEVcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWM2NDAgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTc2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoibHViZW5pY2EiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSB0cmFmZmljIG5ldHdvcmsgaW4gYSBjb3VudHJ5IGNvbnNpc3RzIG9mIE4gY2l0aWVzIChsYWJlbGVkIHdpdGggaW50ZWdlcnMgZnJvbSAxIHRvIE4pIGFuZCBOLTEgcm9hZHMgY29ubmVjdGluZyB0aGUgY2l0aWVzLiBUaGVyZSBpcyBhIHVuaXF1ZSBwYXRoIGJldHdlZW4gZWFjaCBwYWlyIG9mIGRpZmZlcmVudCBjaXRpZXMsIGFuZCB3ZSBrbm93IHRoZSBleGFjdCBsZW5ndGggb2YgZWFjaCByb2FkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsLCBmb3IgZWFjaCBvZiB0aGUgSyBnaXZlbiBwYWlycyBvZiBjaXRpZXMsIGZpbmQgdGhlIGxlbmd0aCBvZiB0aGUgc2hvcnRlc3QgYW5kIHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3Qgcm9hZCBvbiB0aGUgcGF0aCBiZXR3ZWVuIHRoZSB0d28gY2l0aWVzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBOLCAyICZsZTsgTiAmbGU7IDEwMCAwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOLTEgbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgQSwgQiBhbmQgQyBtZWFuaW5nIHRoYXQgdGhlcmUgaXMgYSByb2FkIG9mIGxlbmd0aCBDIGJldHdlZW4gY2l0eSBBIGFuZCBjaXR5IEIuIFRoZSBsZW5ndGggb2YgZWFjaCByb2FkIHdpbGwgYmUgYSBwb3NpdGl2ZSBpbnRlZ2VyIGxlc3MgdGhhbiBvciBlcXVhbCB0byAxIDAwMCAwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBLLCAxICZsZTsgSyAmbGU7IDEwMCAwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBLIGxpbmVzIGNvbnRhaW5zIHR3byBkaWZmZXJlbnQgaW50ZWdlcnMgRCBhbmQgRSAmbmRhc2g7IHRoZSBsYWJlbHMgb2YgdGhlIHR3byBjaXRpZXMgY29uc3RpdHV0aW5nIG9uZSBxdWVyeS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5FYWNoIG9mIHRoZSBLIGxpbmVzIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0d28gaW50ZWdlcnMgJm5kYXNoOyB0aGUgbGVuZ3RocyBmcm9tIHRoZSB0YXNrIGRlc2NyaXB0aW9uIGZvciB0aGUgY29ycmVzcG9uZGluZyBwYWlyIG9mIHRoZSBjaXRpZXMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d