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

문제

n개의 방으로 이루어진 미로가 있다. 이 미로 내의 임의의 두 방 사이에는 반드시 하나의 경로가 존재하고, 그 경로는 유일하다.

이 방들 중 한 방에는 김주성 조교가 보물을 숨겨 놓았는데, 김진영 조교는 이 보물을 찾길 원한다. 그러기 위해서, 김진영 조교는 김주성 조교에게 특정한 방에 보물이 있는지 물어 본다. 친절한 김주성 조교는 김진영 조교가 옳은 방을 골랐으면 그렇다고 말해 주고, 옳은 방을 고르지 않았다면 그 방에 연결된 복도 중 어느 복도를 따라 가야만 보물을 찾을 수 있는지 말해 준다.

여러분이 할 일은 미로의 구조가 주어졌을 때 김진영 조교가 최악의 경우에 몇 번의 질문을 던져야 하는지 계산해 내는 것이다. 물론, 영리한 김진영 조교는 항상 최선의 질문을 한다.

입력

첫째 줄에 n이 주어진다. (1≤n≤50,000) 이후 n-1개의 줄에는 각각 두 개의 숫자가 주어진다. a와 b가 주어졌다면, a번 방과 b번 방 사이에 복도가 있어 왕래할 수 있다는 의미이다. 방의 번호는 1번부터 n번까지 연속해서 붙어 있다.

출력

첫 줄에 김진영 조교가 최선을 다하더라도, 최악의 경우 몇 번의 질문을 던져야 하는지 출력한다.

예제 입력 1

5
1 2
2 3
4 3
5 3

예제 출력 1

2

힌트

처음에 1번 방에 보물이 있는지 질문하면, 어떤 경우에도 두 번의 질문만으로 보물의 위치를 확정지을 수 있다. 처음에 2이나 3번 방에 보물이 있는지 질문해도 좋다. 그러나 처음에 4번이나 5번 방에 보물이 있는지 질문하는 것은 최악의 경우 세 번의 질문이 필요하도록 만든다.

W3sicHJvYmxlbV9pZCI6IjE4NjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWJiM2NcdWNjM2VcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPm5cdWFjMWNcdWM3NTggXHViYzI5XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiZjhcdWI4NWNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViYmY4XHViODVjIFx1YjBiNFx1Yzc1OCBcdWM3ODRcdWM3NThcdWM3NTggXHViNDUwIFx1YmMyOSBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViYzE4XHViNGRjXHVjMmRjIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHVhY2UwLCBcdWFkZjggXHVhY2JkXHViODVjXHViMjk0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YjJlNC48XC9wPlxyXG48cD5cdWM3NzQgXHViYzI5XHViNGU0IFx1YzkxMSBcdWQ1NWMgXHViYzI5XHVjNWQwXHViMjk0IFx1YWU0MFx1YzhmY1x1YzEzMSBcdWM4NzBcdWFkNTBcdWFjMDAgXHViY2Y0XHViYjNjXHVjNzQ0IFx1YzIyOFx1YWNhOCBcdWIxOTNcdWM1NThcdWIyOTRcdWIzNzAsIFx1YWU0MFx1YzljNFx1YzYwMSBcdWM4NzBcdWFkNTBcdWIyOTQgXHVjNzc0IFx1YmNmNFx1YmIzY1x1Yzc0NCBcdWNjM2VcdWFlMzggXHVjNmQwXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWFlNDBcdWM5YzRcdWM2MDEgXHVjODcwXHVhZDUwXHViMjk0IFx1YWU0MFx1YzhmY1x1YzEzMSBcdWM4NzBcdWFkNTBcdWM1ZDBcdWFjOGMgXHVkMmI5XHVjODE1XHVkNTVjIFx1YmMyOVx1YzVkMCBcdWJjZjRcdWJiM2NcdWM3NzQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YmIzY1x1YzViNCBcdWJjZjhcdWIyZTQuIFx1Y2U1Y1x1YzgwOFx1ZDU1YyBcdWFlNDBcdWM4ZmNcdWMxMzEgXHVjODcwXHVhZDUwXHViMjk0IFx1YWU0MFx1YzljNFx1YzYwMSBcdWM4NzBcdWFkNTBcdWFjMDAgXHVjNjMzXHVjNzQwIFx1YmMyOVx1Yzc0NCBcdWFjZThcdWI3OTBcdWM3M2NcdWJhNzQgXHVhZGY4XHViODA3XHViMmU0XHVhY2UwIFx1YjlkMFx1ZDU3NCBcdWM4ZmNcdWFjZTAsIFx1YzYzM1x1Yzc0MCBcdWJjMjlcdWM3NDQgXHVhY2UwXHViOTc0XHVjOWMwIFx1YzU0YVx1YzU1OFx1YjJlNFx1YmE3NCBcdWFkZjggXHViYzI5XHVjNWQwIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWJjZjVcdWIzYzQgXHVjOTExIFx1YzViNFx1YjI5MCBcdWJjZjVcdWIzYzRcdWI5N2MgXHViNTMwXHViNzdjIFx1YWMwMFx1YzU3Y1x1YjljYyBcdWJjZjRcdWJiM2NcdWM3NDQgXHVjYzNlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHViOWQwXHVkNTc0IFx1YzkwMFx1YjJlNC48XC9wPlxyXG48cD5cdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NzQgXHVkNTYwIFx1Yzc3Y1x1Yzc0MCBcdWJiZjhcdWI4NWNcdWM3NTggXHVhZDZjXHVjODcwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHVhZTQwXHVjOWM0XHVjNjAxIFx1Yzg3MFx1YWQ1MFx1YWMwMCBcdWNkNWNcdWM1NDVcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YmE4NyBcdWJjODhcdWM3NTggXHVjOWM4XHViYjM4XHVjNzQ0IFx1YjM1OFx1YzgzOFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVhY2M0XHVjMGIwXHVkNTc0IFx1YjBiNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YmIzY1x1Yjg2MCwgXHVjNjAxXHViOWFjXHVkNTVjIFx1YWU0MFx1YzljNFx1YzYwMSBcdWM4NzBcdWFkNTBcdWIyOTQgXHVkNTZkXHVjMGMxIFx1Y2Q1Y1x1YzEyMFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3NDQgXHVkNTVjXHViMmU0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSZsZTtuJmxlOzUwLDAwMCkgXHVjNzc0XHVkNmM0IG4tMVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gYVx1YzY0MCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1YjJlNFx1YmE3NCwgYVx1YmM4OCBcdWJjMjlcdWFjZmMgYlx1YmM4OCBcdWJjMjkgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YmNmNVx1YjNjNFx1YWMwMCBcdWM3ODhcdWM1YjQgXHVjNjU1XHViNzk4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LiBcdWJjMjlcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgblx1YmM4OFx1YWU0Y1x1YzljMCBcdWM1ZjBcdWMxOGRcdWQ1NzRcdWMxMWMgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVhZTQwXHVjOWM0XHVjNjAxIFx1Yzg3MFx1YWQ1MFx1YWMwMCBcdWNkNWNcdWMxMjBcdWM3NDQgXHViMmU0XHVkNTU4XHViMzU0XHViNzdjXHViM2M0LCBcdWNkNWNcdWM1NDVcdWM3NTggXHVhY2JkXHVjNmIwIFx1YmE4NyBcdWJjODhcdWM3NTggXHVjOWM4XHViYjM4XHVjNzQ0IFx1YjM1OFx1YzgzOFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IjxwPjxpbWcgd2lkdGg9XCIyMTFcIiBoZWlnaHQ9XCIxMThcIiBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwN1wvZmYuUE5HXCIgXC8+PFwvcD5cclxuPHA+XHVjYzk4XHVjNzRjXHVjNWQwIDFcdWJjODggXHViYzI5XHVjNWQwIFx1YmNmNFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjOWM4XHViYjM4XHVkNTU4XHViYTc0LCBcdWM1YjRcdWI1YTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViM2M0IFx1YjQ1MCBcdWJjODhcdWM3NTggXHVjOWM4XHViYjM4XHViOWNjXHVjNzNjXHViODVjIFx1YmNmNFx1YmIzY1x1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVkNjU1XHVjODE1XHVjOWMwXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Y2M5OFx1Yzc0Y1x1YzVkMCAyXHVjNzc0XHViMDk4IDNcdWJjODggXHViYzI5XHVjNWQwIFx1YmNmNFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjOWM4XHViYjM4XHVkNTc0XHViM2M0IFx1Yzg4Ylx1YjJlNC4gXHVhZGY4XHViN2VjXHViMDk4IFx1Y2M5OFx1Yzc0Y1x1YzVkMCA0XHViYzg4XHVjNzc0XHViMDk4IDVcdWJjODggXHViYzI5XHVjNWQwIFx1YmNmNFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjOWM4XHViYjM4XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWNkNWNcdWM1NDVcdWM3NTggXHVhY2JkXHVjNmIwIFx1YzEzOCBcdWJjODhcdWM3NTggXHVjOWM4XHViYjM4XHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWI5Y2NcdWI0ZTBcdWIyZTQuPFwvcD4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4NjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDYXZlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhIGNhdmUgaW4gQnl0ZW90aWEuIEl0IGNvbnNpc3RzIG9mIG4gY2hhbWJlcnMgYW5kIGNvcnJpZG9ycyBjb25uZWN0aW5nIHRoZW0uIFRoZSBjb3JyaWRvcnMgYXJlIGFycmFuZ2VkIGluIHN1Y2ggd2F5LCB0aGF0IHRoZXJlIGlzIGEgdW5pcXVlIHBhdGggYmV0d2VlbiBlYWNoIHBhaXIgb2YgY2hhbWJlcnMuIEluIG9uZSBvZiB0aGVzZSBjaGFtYmVycyBIYW5zZWwgaGFzIGhpZGRlbiBhIHRyZWFzdXJlLCBidXQgaGUgd29uJiMzOTt0IHRlbGwgd2hpY2ggb25lIGl0IGlzLiBHcmV0ZWwgZGVzaXJlcyB0byBrbm93IGl0LiBTbyBzaGUgYXNrcyBIYW5zZWwgYWJvdXQgdmFyaW91cyBjaGFtYmVycy4gV2hlbiBzaGUgZ3Vlc3NlcyByaWdodCBIYW5zZWwgdGVsbHMgaGVyIHNoZSBpcyByaWdodCwgYW5kIHdoZW4gc2hlIGd1ZXNzZXMgd3JvbmcgaGUgdGVsbHMgaGVyIHdoaWNoIHdheSBmcm9tIHRoaXMgY2hhbWJlciBsZWFkcyB0byB0aGUgdHJlYXN1cmUuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbW1lIHRoYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgZnJvbSB0aGUgc3RhbmRhcmQgaW5wdXQgdGhlIGRlc2NyaXB0aW9uIG9mIHRoZSBjYXZlLDxcL2xpPlxyXG5cdDxsaT5maW5kcyB0aGUgbWluaW1hbCBudW1iZXIgb2YgcXVlc3Rpb25zIEdyZXRlbCBoYXMgdG8gYXNrIGluIHRoZSB3b3JzdCBjYXNlIHRvIGxlYXJuIGluIHdoaWNoIGNoYW1iZXIgdGhlIHRyZWFzdXJlIGlzIGhpZGRlbiw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSByZXN1bHQgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IHRoZXJlIGlzIG9uZSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIDEgJmxlOyBuICZsZTsgNTAgMDAwLiBJdCBpcyB0aGUgbnVtYmVyIG9mIGNoYW1iZXJzIGluIHRoZSBjYXZlLiBUaGUgY2hhbWJlcnMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBuLiBJbiB0aGUgZm9sbG93aW5nIG4tMSBsaW5lcyB0aGUgY29ycmlkb3JzIGxpbmtpbmcgdGhlIGNoYW1iZXJzIGFyZSBkZXNjcmliZWQsIG9uZSBwZXIgbGluZS4gRWFjaCBvZiB0aGVzZSBsaW5lcyBjb250YWlucyBhIHBhaXIgb2YgZGlzdGluY3QgcG9zaXRpdmUgaW50ZWdlcnMgYSBhbmQgYiAoMSAmbGU7IGEsYiAmbGU7IG4pLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIEl0IGluZGljYXRlcyB0aGF0IHRoZXJlIGlzIGEgY29ycmlkb3IgYmV0d2VlbiBjaGFtYmVycyBhIGFuZCBiLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW1tZSBzaG91bGQgd3JpdGUgb25lIGludGVnZXIgaW4gdGhlIHN0YW5kYXJkIG91dHB1dCwgdGhlIG1pbmltYWwgbnVtYmVyIG9mIHF1ZXN0aW9ucyBHcmV0ZWwgaGFzIHRvIGFzayBpbiB0aGUgd29yc3QgY2FzZSAoaS5lLiB3ZSBhc3N1bWUgR3JldGVsIGFza3MgdGhlIHF1ZXN0aW9ucyBpbiB0aGUgYmVzdCBwb3NzaWJsZSB3YXksIGJ1dCB0aGUgdHJlYXN1cmUgaXMgaGlkZGVuIGluIHRoZSBjaGFtYmVyIHRoYXQgcmVxdWlyZXMgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHF1ZXN0aW9ucykuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2phc3phZC5naWZcIiBzdHlsZT1cImhlaWdodDoxMDBweDsgd2lkdGg6MTc4cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==