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

문제

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

트리 (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+XHVjNWVjXHViN2VjXHViZDg0XHVjNzc0IFx1ZDU2MCBcdWM3N2NcdWM3NDAgXHVjY2FiXHVjOWY4LCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhZDZjXHVjODcwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCBcdWM3NzRcdWI5N2MgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWM3NTggXHViMTc4XHViMDQ4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI0NThcdWM5ZjhcdWI4NWNcdWIyOTQsIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWIxNzhcdWIwNDhcdWI0ZTRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHViNTRjIFx1YzBhY1x1YzZhOVx1YjQxOFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YjE3OFx1YjA0OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyJmxlO24mbGU7MTAsMDAwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwXHViMjk0IG4tMVx1YWMxY1x1Yzc1OCBcdWI5YzFcdWQwNmNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM1MjlcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc0MCBcdWI5YzFcdWQwNmNcdWFjMDAgXHVjNWYwXHVhY2IwIFx1YzlkM1x1YjI5NCBcdWI0NTAgXHViMTc4XHViNGRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBuXHViYzg4XHVhZTRjXHVjOWMwIFx1YmU2MFx1YzlkMFx1YzVjNlx1Yzc3NCBcdWM1ZjBcdWMxOGRcdWQ1NThcdWM1ZWMgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjJlNC4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3NTggXHViMTc4XHViMDQ4IFx1YWMxY1x1YzIxOFx1YzY0MCwgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWIxNzhcdWIwNDggXHVhZTM4XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIiwiaGludCI6IjxwPjxpbWcgd2lkdGg9XCIzNTZcIiBoZWlnaHQ9XCIyMjlcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwNlwvU2NyZWVuIHNob3QgMjAxMC0wNi0xMSBhdCA0XzUyXzE4IFBNLnBuZ1wiIGFsdD1cIlwiIFwvPjxcL3A+Iiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxODM5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RyaW5ncyIsImRlc2NyaXB0aW9uIjoiPHA+U3RyaW5nLVRveXMgam9pbnQtc3RvY2sgY29tcGFueSBoYXMgYXNrZWQgeW91IGZvciBoZWxwIGluIHNvbHZpbmcgdGhlIGZvbGxvd2luZyBwcm9ibGVtLiBUaGV5IHdhbnQgdG8gbWFudWZhY3R1cmUgbW9kZWxzIG9mIGNvbm5lY3RlZCBhY3ljbGljIGdyYXBocyBtYWRlIG9mIHN0cmluZy48XC9wPlxyXG5cclxuPHA+RWFjaCBncmFwaCBjb25zaXN0cyBvZiB2ZXJ0aWNlcyBhbmQgYSBjZXJ0YWluIG51bWJlciBvZiBlZGdlcyBqb2luaW5nIGRpc3RpbmN0IHZlcnRpY2VzLiBFYWNoIHZlcnRleCBjYW4gYmUgam9pbmVkIHRvIG1hbnkgb3RoZXIgdmVydGljZXMuIEEgZ3JhcGggaXMgY29ubmVjdGVkIGFuZCBhY3ljbGljLCBpZiBldmVyeSB2ZXJ0ZXggY2FuIGJlIHJlYWNoZWQgZnJvbSBldmVyeSBvdGhlciB2ZXJ0ZXggYnkgdHJhdmVsbGluZyBhbG9uZyB0aGUgZWRnZXMgYW5kIGZ1cnRoZXJtb3JlIHRoZXJlIGlzIGEgdW5pcXVlIHdheSBvZiBkb2luZyBzbyB3aXRob3V0IHR1cm5pbmcgYmFjay48XC9wPlxyXG5cclxuPHA+R3JhcGhzJiMzOTsgdmVydGljZXMgYXJlIHRvIGJlIG1vZGVsbGVkIGJ5IG5vZGVzIGtub3R0ZWQgb24gYml0cyBvZiBzdHJpbmcsIHdoaWxlIGVkZ2VzIGJ5IHRoZSBiaXRzIG9mIHN0cmluZyB0aGVtc2VsdmVzIGJldHdlZW4gdGhlIG5vZGVzLiBFYWNoIG5vZGUgY2FuIGJlIGVpdGhlciBhIGtub3Qgb24gYSBzaW5nbGUgYml0IG9mIHN0cmluZyBvciBtYW55IGJpdHMga25vdHRlZCBhdCBvbmUgcG9pbnQuIER1ZSB0byB0ZWNobmljYWwgcmVhc29ucyBjb3N0IG9mIHByb2R1Y3Rpb24gZGVwZW5kcyBvbiB0aGUgbnVtYmVyIG9mIHN0cmluZyBiaXRzIHVzZWQgaW4gbWFraW5nIGEgbW9kZWwgYW5kIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBiaXQuIChFYWNoIGVkZ2UgaGFzIGxlbmd0aCBvZiAxLiBMZW5ndGggb2Ygc3RyaW5nIHVzZWQgdG8gbWFraW5nIGEga25vdCBpcyBuZWdsaWdpYmxlLik8XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW1tZSB0aGF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0IHRoZSBkZXNjcmlwdGlvbiBvZiBhIGNvbm5lY3RlZCBhY3ljbGljIGdyYXBoIHRvIGJlIG1vZGVsbGVkLDxcL2xpPlxyXG5cdDxsaT5jYWxjdWxhdGVzOlxyXG5cdDx1bD5cclxuXHRcdDxsaT50aGUgbWluaW1hbCBudW1iZXIgb2Ygc3RyaW5nIGJpdHMgbmVjZXNzYXJ5IHRvIG1ha2luZyB0aGUgbW9kZWwsPFwvbGk+XHJcblx0XHQ8bGk+YXNzdW1pbmcgdGhhdCB0aGUgbnVtYmVyIG9mIHN0cmluZyBiaXQgaXMgbWluaW1hbCwgdGhlIG1pbmltYWwgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHN0cmluZyBiaXQgbmVlZGVkIHRvIG1ha2luZyB0aGUgbW9kZWwuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgb2J0YWluZWQgbnVtYmVycyB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBvbmUgcG9zaXRpdmUgaW50ZWdlciBuIC0gdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBpbiB0aGUgZ3JhcGgsIDIgJmxlOyBuICZsZTsgMTAgMDAwLiBWZXJ0aWNlcyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIG4uIFRoZSBmb2xsb3dpbmcgbi0xIGxpbmVzIGNvbnRhaW4gZGVzY3JpcHRpb25zIG9mIGVkZ2VzLCBvbmUgcGVyIGxpbmUuIEVhY2ggb2YgdGhlc2UgbGluZXMgY29udGFpbnMgYSBwYWlyIG9mIGludGVnZXJzIGEgYW5kIGIgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCAxICZsZTsgYSxiICZsZTsgbiwgYSAmbmU7IGIuIFN1Y2ggcGFpciByZXByZXNlbnRzIGFuIGVkZ2Ugam9pbmluZyB2ZXJ0aWNlcyBhIGFuZCBiLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW1tZSBzaG91bGQgd3JpdGUgdHdvIGludGVnZXJzIGsgYW5kIGwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBvdXRwdXQ6IGsgc2hvdWxkIGJlIHRoZSBtaW5pbWFsIG51bWJlciBvZiBzdHJpbmcgYml0cyByZXF1aXJlZCB0byBtYWtlIHRoZSBncmFwaCYjMzk7cyBtb2RlbCwgd2hpbGUgbCBzaG91bGQgYmUgdGhlIG1pbmltYWwgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHN0cmluZyBiaXQgKGFzc3VtaW5nIHRoYXQgayBzdHJpbmcgYml0cyBhcmUgdXNlZCkuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3N6bi5naWZcIiBzdHlsZT1cImhlaWdodDoxOTBweDsgd2lkdGg6MzAycHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==