시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 65 27 19 33.333%

문제

월드 장난감 회사는 노끈들을 이용해서 트리의 모형을 만들고자 한다. 이를 돕기 위한 프로그램을 작성하라.

트리 (tree)는 그래프 (graph)의 일종으로, 연결되어 있으며, 내부에 싸이클이 존재하지 않는 그래프이다. 그래프에서 버텍스 (vertex), 에지 (edge)라고 부르는 것을, 트리에 한해서는 각각 노드 (node)와 링크 (link)라고 부른다.

트리의 노드들은 노끈 위에 매인 매듭으로 표현되고, 각 매듭 사이를 연결하는 노끈이 트리의 링크들을 표현한다. 노드를 표현하는 매듭들은 그냥 한 개의 노끈 중간이나 끝부분을 묶은 것일 수도 있고, 여러 개의 노끈들이 한 점에서 뭉쳐 묶여 있는 부분일 수도 있다.

기술적인 문제 때문에, 생산 단가는 모델을 만드는 데 사용되는 노끈의 개수와, 사용된 노끈들 중 가장 긴 노끈의 길이에 의존한다. (각각의 링크들은 길이가 모두 1이다. 매듭을 만드는 데 소요되는 노끈의 길이는 무시한다.)

여러분이 할 일은 첫째, 트리의 구조가 주어지면 이를 만들기 위한 최소의 노끈 개수를 구하는 것이다. 둘째로는, 이와 같이 최소 개수의 노끈들을 이용하여 트리를 만들 때 사용되는 가장 긴 노끈 길이의 최솟값을 구하는 것이다.

입력

첫째 줄에 노드의 개수를 나타내는 양의 정수 n이 주어진다. (2≤n≤10,000) 둘째 줄부터는 n-1개의 링크를 나타내는 두 개씩의 양의 정수가 주어진다. 각각은 링크가 연결 짓는 두 노드의 번호를 나타낸다. 노드의 번호는 1번부터 n번까지 빠짐없이 연속하여 붙어 있다.

출력

첫 줄에 필요한 최소한의 노끈 개수와, 가장 긴 노끈 길이의 최솟값을 출력한다.

예제 입력 1

9
7 8
4 5
5 6
1 2
3 2
9 8
2 5
5 8

예제 출력 1

4 2

힌트

W3sicHJvYmxlbV9pZCI6IjE4MzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWMgXHViYWE4XHViMzc4IFx1YjljY1x1YjRlNFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNmQ0XHViNGRjIFx1YzdhNVx1YjA5Y1x1YWMxMCBcdWQ2OGNcdWMwYWNcdWIyOTQgXHViMTc4XHViMDQ4XHViNGU0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWQyYjhcdWI5YWNcdWM3NTggXHViYWE4XHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWIzZDVcdWFlMzAgXHVjNzA0XHVkNTVjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD48cD5cdWQyYjhcdWI5YWMgKHRyZWUpXHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNCAoZ3JhcGgpXHVjNzU4IFx1Yzc3Y1x1Yzg4NVx1YzczY1x1Yjg1YywgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViMGI0XHViZDgwXHVjNWQwIFx1YzJmOFx1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViNzk4XHVkNTA0XHVjNWQwXHVjMTFjIFx1YmM4NFx1ZDE0ZFx1YzJhNCAodmVydGV4KSwgXHVjNWQwXHVjOWMwIChlZGdlKVx1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzRcdWIyOTQgXHVhYzgzXHVjNzQ0LCBcdWQyYjhcdWI5YWNcdWM1ZDAgXHVkNTVjXHVkNTc0XHVjMTFjXHViMjk0IFx1YWMwMVx1YWMwMSBcdWIxNzhcdWI0ZGMgKG5vZGUpXHVjNjQwIFx1YjljMVx1ZDA2YyAobGluaylcdWI3N2NcdWFjZTAgXHViZDgwXHViOTc4XHViMmU0LjxcL3A+PHA+XHVkMmI4XHViOWFjXHVjNzU4IFx1YjE3OFx1YjRkY1x1YjRlNFx1Yzc0MCBcdWIxNzhcdWIwNDggXHVjNzA0XHVjNWQwIFx1YjllNFx1Yzc3OCBcdWI5ZTRcdWI0ZWRcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDE4XHVhY2UwLCBcdWFjMDEgXHViOWU0XHViNGVkIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViMTc4XHViMDQ4XHVjNzc0IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWI5YzFcdWQwNmNcdWI0ZTRcdWM3NDQgXHVkNDVjXHVkNjA0XHVkNTVjXHViMmU0LiBcdWIxNzhcdWI0ZGNcdWI5N2MgXHVkNDVjXHVkNjA0XHVkNTU4XHViMjk0IFx1YjllNFx1YjRlZFx1YjRlNFx1Yzc0MCBcdWFkZjhcdWIwZTUgXHVkNTVjIFx1YWMxY1x1Yzc1OCBcdWIxNzhcdWIwNDggXHVjOTExXHVhYzA0XHVjNzc0XHViMDk4IFx1YjA1ZFx1YmQ4MFx1YmQ4NFx1Yzc0NCBcdWJiMzZcdWM3NDAgXHVhYzgzXHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWFjZTAsIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViMTc4XHViMDQ4XHViNGU0XHVjNzc0IFx1ZDU1YyBcdWM4MTBcdWM1ZDBcdWMxMWMgXHViYjQ5XHVjY2QwIFx1YmIzNlx1YzVlYyBcdWM3ODhcdWIyOTQgXHViZDgwXHViZDg0XHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD48cD5cdWFlMzBcdWMyMjBcdWM4MDFcdWM3NzggXHViYjM4XHVjODFjIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjMGRkXHVjMGIwIFx1YjJlOFx1YWMwMFx1YjI5NCBcdWJhYThcdWIzNzhcdWM3NDQgXHViOWNjXHViNGRjXHViMjk0IFx1YjM3MCBcdWMwYWNcdWM2YTlcdWI0MThcdWIyOTQgXHViMTc4XHViMDQ4XHVjNzU4IFx1YWMxY1x1YzIxOFx1YzY0MCwgXHVjMGFjXHVjNmE5XHViNDFjIFx1YjE3OFx1YjA0OFx1YjRlNCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWIxNzhcdWIwNDhcdWM3NTggXHVhZTM4XHVjNzc0XHVjNWQwIFx1Yzc1OFx1Yzg3NFx1ZDU1Y1x1YjJlNC4gKFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWI5YzFcdWQwNmNcdWI0ZTRcdWM3NDAgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YmFhOFx1YjQ1MCAxXHVjNzc0XHViMmU0LiBcdWI5ZTRcdWI0ZWRcdWM3NDQgXHViOWNjXHViNGRjXHViMjk0IFx1YjM3MCBcdWMxOGNcdWM2OTRcdWI0MThcdWIyOTQgXHViMTc4XHViMDQ4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWJiMzRcdWMyZGNcdWQ1NWNcdWIyZTQuKTxcL3A+PHA+XHVjNWVjXHViN2VjXHViZDg0XHVjNzc0IFx1ZDU2MCBcdWM3N2NcdWM3NDAgXHVjY2FiXHVjOWY4LCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhZDZjXHVjODcwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCBcdWM3NzRcdWI5N2MgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWM3NTggXHViMTc4XHViMDQ4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI0NThcdWM5ZjhcdWI4NWNcdWIyOTQsIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWIxNzhcdWIwNDhcdWI0ZTRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHViNTRjIFx1YzBhY1x1YzZhOVx1YjQxOFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YjE3OFx1YjA0OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyJmxlO24mbGU7MTAsMDAwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwXHViMjk0IG4tMVx1YWMxY1x1Yzc1OCBcdWI5YzFcdWQwNmNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM1MjlcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc0MCBcdWI5YzFcdWQwNmNcdWFjMDAgXHVjNWYwXHVhY2IwIFx1YzlkM1x1YjI5NCBcdWI0NTAgXHViMTc4XHViNGRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBuXHViYzg4XHVhZTRjXHVjOWMwIFx1YmU2MFx1YzlkMFx1YzVjNlx1Yzc3NCBcdWM1ZjBcdWMxOGRcdWQ1NThcdWM1ZWMgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjJlNC4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3NTggXHViMTc4XHViMDQ4IFx1YWMxY1x1YzIxOFx1YzY0MCwgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWIxNzhcdWIwNDggXHVhZTM4XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIiwiaGludCI6IjxwPjxpbWcgd2lkdGg9XCIzNTZcIiBoZWlnaHQ9XCIyMjlcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwNlwvU2NyZWVuIHNob3QgMjAxMC0wNi0xMSBhdCA0XzUyXzE4IFBNLnBuZ1wiIGFsdD1cIlwiIFwvPjxcL3A+Iiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4MzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdHJpbmdzIiwiZGVzY3JpcHRpb24iOiI8cD5TdHJpbmctVG95cyBqb2ludC1zdG9jayBjb21wYW55IGhhcyBhc2tlZCB5b3UgZm9yIGhlbHAgaW4gc29sdmluZyB0aGUgZm9sbG93aW5nIHByb2JsZW0uIFRoZXkgd2FudCB0byBtYW51ZmFjdHVyZSBtb2RlbHMgb2YgY29ubmVjdGVkIGFjeWNsaWMgZ3JhcGhzIG1hZGUgb2Ygc3RyaW5nLjxcL3A+XHJcblxyXG48cD5FYWNoIGdyYXBoIGNvbnNpc3RzIG9mIHZlcnRpY2VzIGFuZCBhIGNlcnRhaW4gbnVtYmVyIG9mIGVkZ2VzIGpvaW5pbmcgZGlzdGluY3QgdmVydGljZXMuIEVhY2ggdmVydGV4IGNhbiBiZSBqb2luZWQgdG8gbWFueSBvdGhlciB2ZXJ0aWNlcy4gQSBncmFwaCBpcyBjb25uZWN0ZWQgYW5kIGFjeWNsaWMsIGlmIGV2ZXJ5IHZlcnRleCBjYW4gYmUgcmVhY2hlZCBmcm9tIGV2ZXJ5IG90aGVyIHZlcnRleCBieSB0cmF2ZWxsaW5nIGFsb25nIHRoZSBlZGdlcyBhbmQgZnVydGhlcm1vcmUgdGhlcmUgaXMgYSB1bmlxdWUgd2F5IG9mIGRvaW5nIHNvIHdpdGhvdXQgdHVybmluZyBiYWNrLjxcL3A+XHJcblxyXG48cD5HcmFwaHMmIzM5OyB2ZXJ0aWNlcyBhcmUgdG8gYmUgbW9kZWxsZWQgYnkgbm9kZXMga25vdHRlZCBvbiBiaXRzIG9mIHN0cmluZywgd2hpbGUgZWRnZXMgYnkgdGhlIGJpdHMgb2Ygc3RyaW5nIHRoZW1zZWx2ZXMgYmV0d2VlbiB0aGUgbm9kZXMuIEVhY2ggbm9kZSBjYW4gYmUgZWl0aGVyIGEga25vdCBvbiBhIHNpbmdsZSBiaXQgb2Ygc3RyaW5nIG9yIG1hbnkgYml0cyBrbm90dGVkIGF0IG9uZSBwb2ludC4gRHVlIHRvIHRlY2huaWNhbCByZWFzb25zIGNvc3Qgb2YgcHJvZHVjdGlvbiBkZXBlbmRzIG9uIHRoZSBudW1iZXIgb2Ygc3RyaW5nIGJpdHMgdXNlZCBpbiBtYWtpbmcgYSBtb2RlbCBhbmQgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IGJpdC4gKEVhY2ggZWRnZSBoYXMgbGVuZ3RoIG9mIDEuIExlbmd0aCBvZiBzdHJpbmcgdXNlZCB0byBtYWtpbmcgYSBrbm90IGlzIG5lZ2xpZ2libGUuKTxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRvIHdyaXRlIGEgcHJvZ3JhbW1lIHRoYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgZnJvbSB0aGUgc3RhbmRhcmQgaW5wdXQgdGhlIGRlc2NyaXB0aW9uIG9mIGEgY29ubmVjdGVkIGFjeWNsaWMgZ3JhcGggdG8gYmUgbW9kZWxsZWQsPFwvbGk+XHJcblx0PGxpPmNhbGN1bGF0ZXM6XHJcblx0PHVsPlxyXG5cdFx0PGxpPnRoZSBtaW5pbWFsIG51bWJlciBvZiBzdHJpbmcgYml0cyBuZWNlc3NhcnkgdG8gbWFraW5nIHRoZSBtb2RlbCw8XC9saT5cclxuXHRcdDxsaT5hc3N1bWluZyB0aGF0IHRoZSBudW1iZXIgb2Ygc3RyaW5nIGJpdCBpcyBtaW5pbWFsLCB0aGUgbWluaW1hbCBsZW5ndGggb2YgdGhlIGxvbmdlc3Qgc3RyaW5nIGJpdCBuZWVkZWQgdG8gbWFraW5nIHRoZSBtb2RlbC48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSBvYnRhaW5lZCBudW1iZXJzIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIG9uZSBwb3NpdGl2ZSBpbnRlZ2VyIG4gLSB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIHRoZSBncmFwaCwgMiAmbGU7IG4gJmxlOyAxMCAwMDAuIFZlcnRpY2VzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbi4gVGhlIGZvbGxvd2luZyBuLTEgbGluZXMgY29udGFpbiBkZXNjcmlwdGlvbnMgb2YgZWRnZXMsIG9uZSBwZXIgbGluZS4gRWFjaCBvZiB0aGVzZSBsaW5lcyBjb250YWlucyBhIHBhaXIgb2YgaW50ZWdlcnMgYSBhbmQgYiBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIDEgJmxlOyBhLGIgJmxlOyBuLCBhICZuZTsgYi4gU3VjaCBwYWlyIHJlcHJlc2VudHMgYW4gZWRnZSBqb2luaW5nIHZlcnRpY2VzIGEgYW5kIGIuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbW1lIHNob3VsZCB3cml0ZSB0d28gaW50ZWdlcnMgayBhbmQgbCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UgaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIG91dHB1dDogayBzaG91bGQgYmUgdGhlIG1pbmltYWwgbnVtYmVyIG9mIHN0cmluZyBiaXRzIHJlcXVpcmVkIHRvIG1ha2UgdGhlIGdyYXBoJiMzOTtzIG1vZGVsLCB3aGlsZSBsIHNob3VsZCBiZSB0aGUgbWluaW1hbCBsZW5ndGggb2YgdGhlIGxvbmdlc3Qgc3RyaW5nIGJpdCAoYXNzdW1pbmcgdGhhdCBrIHN0cmluZyBiaXRzIGFyZSB1c2VkKS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc3puLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjE5MHB4OyB3aWR0aDozMDJweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=