시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB6661158429.577%

문제

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번 방에 보물이 있는지 질문하는 것은 최악의 경우 세 번의 질문이 필요하도록 만든다.

W3sicHJvYmxlbV9pZCI6IjE4NjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWJiM2NcdWNjM2VcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPm5cdWFjMWNcdWM3NTggXHViYzI5XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiZjhcdWI4NWNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViYmY4XHViODVjIFx1YjBiNFx1Yzc1OCBcdWM3ODRcdWM3NThcdWM3NTggXHViNDUwIFx1YmMyOSBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViYzE4XHViNGRjXHVjMmRjIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHVhY2UwLCBcdWFkZjggXHVhY2JkXHViODVjXHViMjk0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YmMyOVx1YjRlNCBcdWM5MTEgXHVkNTVjIFx1YmMyOVx1YzVkMFx1YjI5NCBcdWFlNDBcdWM4ZmNcdWMxMzEgXHVjODcwXHVhZDUwXHVhYzAwIFx1YmNmNFx1YmIzY1x1Yzc0NCBcdWMyMjhcdWFjYTggXHViMTkzXHVjNTU4XHViMjk0XHViMzcwLCBcdWFlNDBcdWM5YzRcdWM2MDEgXHVjODcwXHVhZDUwXHViMjk0IFx1Yzc3NCBcdWJjZjRcdWJiM2NcdWM3NDQgXHVjYzNlXHVhZTM4IFx1YzZkMFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2VjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHVhZTQwXHVjOWM0XHVjNjAxIFx1Yzg3MFx1YWQ1MFx1YjI5NCBcdWFlNDBcdWM4ZmNcdWMxMzEgXHVjODcwXHVhZDUwXHVjNWQwXHVhYzhjIFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWJjMjlcdWM1ZDAgXHViY2Y0XHViYjNjXHVjNzc0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWJiM2NcdWM1YjQgXHViY2Y4XHViMmU0LiBcdWNlNWNcdWM4MDhcdWQ1NWMgXHVhZTQwXHVjOGZjXHVjMTMxIFx1Yzg3MFx1YWQ1MFx1YjI5NCBcdWFlNDBcdWM5YzRcdWM2MDEgXHVjODcwXHVhZDUwXHVhYzAwIFx1YzYzM1x1Yzc0MCBcdWJjMjlcdWM3NDQgXHVhY2U4XHViNzkwXHVjNzNjXHViYTc0IFx1YWRmOFx1YjgwN1x1YjJlNFx1YWNlMCBcdWI5ZDBcdWQ1NzQgXHVjOGZjXHVhY2UwLCBcdWM2MzNcdWM3NDAgXHViYzI5XHVjNzQ0IFx1YWNlMFx1Yjk3NFx1YzljMCBcdWM1NGFcdWM1NThcdWIyZTRcdWJhNzQgXHVhZGY4IFx1YmMyOVx1YzVkMCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHViY2Y1XHViM2M0IFx1YzkxMSBcdWM1YjRcdWIyOTAgXHViY2Y1XHViM2M0XHViOTdjIFx1YjUzMFx1Yjc3YyBcdWFjMDBcdWM1N2NcdWI5Y2MgXHViY2Y0XHViYjNjXHVjNzQ0IFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YjlkMFx1ZDU3NCBcdWM5MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc3NCBcdWQ1NjAgXHVjNzdjXHVjNzQwIFx1YmJmOFx1Yjg1Y1x1Yzc1OCBcdWFkNmNcdWM4NzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWFlNDBcdWM5YzRcdWM2MDEgXHVjODcwXHVhZDUwXHVhYzAwIFx1Y2Q1Y1x1YzU0NVx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViYTg3IFx1YmM4OFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3NDQgXHViMzU4XHVjODM4XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWFjYzRcdWMwYjBcdWQ1NzQgXHViMGI0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViYjNjXHViODYwLCBcdWM2MDFcdWI5YWNcdWQ1NWMgXHVhZTQwXHVjOWM0XHVjNjAxIFx1Yzg3MFx1YWQ1MFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjZDVjXHVjMTIwXHVjNzU4IFx1YzljOFx1YmIzOFx1Yzc0NCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyA1MCwwMDApIFx1Yzc3NFx1ZDZjNCBuLTFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGFcdWM2NDAgYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWIyZTRcdWJhNzQsIGFcdWJjODggXHViYzI5XHVhY2ZjIGJcdWJjODggXHViYzI5IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWJjZjVcdWIzYzRcdWFjMDAgXHVjNzg4XHVjNWI0IFx1YzY1NVx1Yjc5OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gXHViYzI5XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIG5cdWJjODhcdWFlNGNcdWM5YzAgXHVjNWYwXHVjMThkXHVkNTc0XHVjMTFjIFx1YmQ5OVx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWFlNDBcdWM5YzRcdWM2MDEgXHVjODcwXHVhZDUwXHVhYzAwIFx1Y2Q1Y1x1YzEyMFx1Yzc0NCBcdWIyZTRcdWQ1NThcdWIzNTRcdWI3N2NcdWIzYzQsIFx1Y2Q1Y1x1YzU0NVx1Yzc1OCBcdWFjYmRcdWM2YjAgXHViYTg3IFx1YmM4OFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3NDQgXHViMzU4XHVjODM4XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgaGVpZ2h0PVwiMTE4XCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDdcL2ZmLlBOR1wiIHdpZHRoPVwiMjExXCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1Y2M5OFx1Yzc0Y1x1YzVkMCAxXHViYzg4IFx1YmMyOVx1YzVkMCBcdWJjZjRcdWJiM2NcdWM3NzQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YzljOFx1YmIzOFx1ZDU1OFx1YmE3NCwgXHVjNWI0XHViNWE0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjNjNCBcdWI0NTAgXHViYzg4XHVjNzU4IFx1YzljOFx1YmIzOFx1YjljY1x1YzczY1x1Yjg1YyBcdWJjZjRcdWJiM2NcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1ZDY1NVx1YzgxNVx1YzljMFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWNjOThcdWM3NGNcdWM1ZDAgMlx1Yzc3NFx1YjA5OCAzXHViYzg4IFx1YmMyOVx1YzVkMCBcdWJjZjRcdWJiM2NcdWM3NzQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YzljOFx1YmIzOFx1ZDU3NFx1YjNjNCBcdWM4OGJcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCBcdWNjOThcdWM3NGNcdWM1ZDAgNFx1YmM4OFx1Yzc3NFx1YjA5OCA1XHViYzg4IFx1YmMyOVx1YzVkMCBcdWJjZjRcdWJiM2NcdWM3NzQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YzljOFx1YmIzOFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjZDVjXHVjNTQ1XHVjNzU4IFx1YWNiZFx1YzZiMCBcdWMxMzggXHViYzg4XHVjNzU4IFx1YzljOFx1YmIzOFx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIzYzRcdWI4NWQgXHViOWNjXHViNGUwXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTg2OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNhdmUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGlzIGEgY2F2ZSBpbiBCeXRlb3RpYS4gSXQgY29uc2lzdHMgb2YgbiBjaGFtYmVycyBhbmQgY29ycmlkb3JzIGNvbm5lY3RpbmcgdGhlbS4gVGhlIGNvcnJpZG9ycyBhcmUgYXJyYW5nZWQgaW4gc3VjaCB3YXksIHRoYXQgdGhlcmUgaXMgYSB1bmlxdWUgcGF0aCBiZXR3ZWVuIGVhY2ggcGFpciBvZiBjaGFtYmVycy4gSW4gb25lIG9mIHRoZXNlIGNoYW1iZXJzIEhhbnNlbCBoYXMgaGlkZGVuIGEgdHJlYXN1cmUsIGJ1dCBoZSB3b24mIzM5O3QgdGVsbCB3aGljaCBvbmUgaXQgaXMuIEdyZXRlbCBkZXNpcmVzIHRvIGtub3cgaXQuIFNvIHNoZSBhc2tzIEhhbnNlbCBhYm91dCB2YXJpb3VzIGNoYW1iZXJzLiBXaGVuIHNoZSBndWVzc2VzIHJpZ2h0IEhhbnNlbCB0ZWxscyBoZXIgc2hlIGlzIHJpZ2h0LCBhbmQgd2hlbiBzaGUgZ3Vlc3NlcyB3cm9uZyBoZSB0ZWxscyBoZXIgd2hpY2ggd2F5IGZyb20gdGhpcyBjaGFtYmVyIGxlYWRzIHRvIHRoZSB0cmVhc3VyZS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtbWUgdGhhdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIGNhdmUsPFwvbGk+XHJcblx0PGxpPmZpbmRzIHRoZSBtaW5pbWFsIG51bWJlciBvZiBxdWVzdGlvbnMgR3JldGVsIGhhcyB0byBhc2sgaW4gdGhlIHdvcnN0IGNhc2UgdG8gbGVhcm4gaW4gd2hpY2ggY2hhbWJlciB0aGUgdHJlYXN1cmUgaXMgaGlkZGVuLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIHJlc3VsdCB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgdGhlcmUgaXMgb25lIHBvc2l0aXZlIGludGVnZXIgbiwgMSAmbGU7IG4gJmxlOyA1MCAwMDAuIEl0IGlzIHRoZSBudW1iZXIgb2YgY2hhbWJlcnMgaW4gdGhlIGNhdmUuIFRoZSBjaGFtYmVycyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIG4uIEluIHRoZSBmb2xsb3dpbmcgbi0xIGxpbmVzIHRoZSBjb3JyaWRvcnMgbGlua2luZyB0aGUgY2hhbWJlcnMgYXJlIGRlc2NyaWJlZCwgb25lIHBlciBsaW5lLiBFYWNoIG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zIGEgcGFpciBvZiBkaXN0aW5jdCBwb3NpdGl2ZSBpbnRlZ2VycyBhIGFuZCBiICgxICZsZTsgYSxiICZsZTsgbiksIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gSXQgaW5kaWNhdGVzIHRoYXQgdGhlcmUgaXMgYSBjb3JyaWRvciBiZXR3ZWVuIGNoYW1iZXJzIGEgYW5kIGIuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbW1lIHNob3VsZCB3cml0ZSBvbmUgaW50ZWdlciBpbiB0aGUgc3RhbmRhcmQgb3V0cHV0LCB0aGUgbWluaW1hbCBudW1iZXIgb2YgcXVlc3Rpb25zIEdyZXRlbCBoYXMgdG8gYXNrIGluIHRoZSB3b3JzdCBjYXNlIChpLmUuIHdlIGFzc3VtZSBHcmV0ZWwgYXNrcyB0aGUgcXVlc3Rpb25zIGluIHRoZSBiZXN0IHBvc3NpYmxlIHdheSwgYnV0IHRoZSB0cmVhc3VyZSBpcyBoaWRkZW4gaW4gdGhlIGNoYW1iZXIgdGhhdCByZXF1aXJlcyB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgcXVlc3Rpb25zKS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvamFzemFkLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjEwMHB4OyB3aWR0aDoxNzhweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Polish Olympiad in Informatics > POI 2003/2004 > Stage 2 3번