문제
KSA에는 1ドル$번부터 $N$번까지의 건물이 있고 두 건물 사이를 양방향으로 연결하는 $N-1$개의 통로가 있다. $i$번 통로는 $A_i$번 건물과 $B_i$번 건물을 연결하며 임의의 건물에서 다른 건물로 가는 경로가 항상 존재한다. 민찬이와 에릭은 여기서 숨바꼭질하고 있다. 민찬이가 술래고 1ドル$번부터 $N$번 건물 중 어딘가에 숨은 에릭을 찾아야 한다.
민찬이는 남몰래 에릭의 옷에 숨겨놓았던 위치 추적 장치의 도움을 받아 숨바꼭질에서 이기려고 한다. 이 위치 추적 장치는 다음과 같은 방법으로만 위치를 알려준다.
- 위치 추적 장치의 리모컨에 정수 $x$ $(1 \leq x \leq N)$를 입력하면 $x$번 건물에서부터 에릭이 숨어있는 건물까지 가기 위해 지나야 할 최소 통로 수를 화면에 띄워준다.
위치 추적 장치의 배터리가 얼마 남지 않았기 때문에 민찬이는 위치 추적 장치를 많이 사용할 수 없다. 다음 행동을 $k$번 해서 에릭이 숨어있는 건물을 알 수 있는 가장 작은 $k$를 구해보자.
- 어떤 수 $x$ $(1 \leq x \leq N)$를 선택해서 리모컨에 입력한 후, 리모컨에 띄워지는 수를 확인한다.
단, 민찬이는 다음 행동을 결정할 때, 그 전 행동들에서 얻은 정보를 사용할 수 있다.
출력
에릭이 숨어있는 건물을 알기 위한 최소의 $k$를 출력한다.
제한
- 2ドル \leq N \leq 2000$
- 1ドル \leq A_i < B_i \leq N$ $(1 \leq i \leq N-1)$
- 1ドル \leq i < j \leq N$인 모든 $i,ドル $j$에 대해서 $i$번 건물과 $j$번 건물을 연결하는 경로가 존재
서브태스크
| 번호 | 배점 | 제한 | | 1 | 7 | $A_i = 1$ $(1 \leq i \leq N-1)$
|
| 2 | 44 | $N \leq 100$
|
| 3 | 49 | 추가 제약 조건 없음
|
리모컨에 2ドル$번을 입력해서 한 번 만에 에릭이 숨어있는 건물을 알 수 있다.
W3sicHJvYmxlbV9pZCI6IjI5MjA0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiS1NBXHVjNWQwXHVjMTFjIFx1YzIyOFx1YmMxNFx1YWYyZFx1YzljOCIsImRlc2NyaXB0aW9uIjoiPHA+S1NBXHVjNWQwXHViMjk0ICQxJFx1YmM4OFx1YmQ4MFx1ZDEzMCAkTiRcdWJjODhcdWFlNGNcdWM5YzBcdWM3NTggXHVhYzc0XHViYjNjXHVjNzc0IFx1Yzc4OFx1YWNlMCBcdWI0NTAgXHVhYzc0XHViYjNjIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM1OTFcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0ICROLTEkXHVhYzFjXHVjNzU4IFx1ZDFiNVx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTQuICRpJFx1YmM4OCBcdWQxYjVcdWI4NWNcdWIyOTQgJEFfaSRcdWJjODggXHVhYzc0XHViYjNjXHVhY2ZjICRCX2kkXHViYzg4IFx1YWM3NFx1YmIzY1x1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWJhNzAgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YWM3NFx1YmIzY1x1YzVkMFx1YzExYyBcdWIyZTRcdWI5NzggXHVhYzc0XHViYjNjXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVkNTZkXHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gXHViYmZjXHVjYzJjXHVjNzc0XHVjNjQwIFx1YzVkMFx1YjlhZFx1Yzc0MCBcdWM1ZWNcdWFlMzBcdWMxMWMgXHVjMjI4XHViYzE0XHVhZjJkXHVjOWM4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViYmZjXHVjYzJjXHVjNzc0XHVhYzAwIFx1YzIyMFx1Yjc5OFx1YWNlMCAkMSRcdWJjODhcdWJkODBcdWQxMzAgJE4kXHViYzg4IFx1YWM3NFx1YmIzYyBcdWM5MTEgXHVjNWI0XHViNTE4XHVhYzAwXHVjNWQwIFx1YzIyOFx1Yzc0MCBcdWM1ZDBcdWI5YWRcdWM3NDQgXHVjYzNlXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYmZjXHVjYzJjXHVjNzc0XHViMjk0IFx1YjBhOFx1YmFiMFx1Yjc5OCBcdWM1ZDBcdWI5YWRcdWM3NTggXHVjNjM3XHVjNWQwIFx1YzIyOFx1YWNhOFx1YjE5M1x1YzU1OFx1YjM1OCBcdWM3MDRcdWNlNTggXHVjZDk0XHVjODAxIFx1YzdhNVx1Y2U1OFx1Yzc1OCBcdWIzYzRcdWM2YzBcdWM3NDQgXHViYzFiXHVjNTQ0IFx1YzIyOFx1YmMxNFx1YWYyZFx1YzljOFx1YzVkMFx1YzExYyBcdWM3NzRcdWFlMzBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVjNzA0XHVjZTU4IFx1Y2Q5NFx1YzgwMSBcdWM3YTVcdWNlNThcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWNcdWI5Y2MgXHVjNzA0XHVjZTU4XHViOTdjIFx1YzU0Y1x1YjgyNFx1YzkwMFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM3MDRcdWNlNTggXHVjZDk0XHVjODAxIFx1YzdhNVx1Y2U1OFx1Yzc1OCBcdWI5YWNcdWJhYThcdWNlZThcdWM1ZDAgXHVjODE1XHVjMjE4ICR4JCAkKDEgXFxsZXEgeCBcXGxlcSBOKSRcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHViYTc0ICR4JFx1YmM4OCBcdWFjNzRcdWJiM2NcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjNWQwXHViOWFkXHVjNzc0IFx1YzIyOFx1YzViNFx1Yzc4OFx1YjI5NCBcdWFjNzRcdWJiM2NcdWFlNGNcdWM5YzAgXHVhYzAwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM5YzBcdWIwOThcdWM1N2MgXHVkNTYwIFx1Y2Q1Y1x1YzE4YyBcdWQxYjVcdWI4NWMgXHVjMjE4XHViOTdjIFx1ZDY1NFx1YmE3NFx1YzVkMCBcdWI3NDRcdWM2Y2NcdWM5MDBcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzA0XHVjZTU4IFx1Y2Q5NFx1YzgwMSBcdWM3YTVcdWNlNThcdWM3NTggXHViYzMwXHVkMTMwXHViOWFjXHVhYzAwIFx1YzViY1x1YjljOCBcdWIwYThcdWM5YzAgXHVjNTRhXHVjNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJiZmNcdWNjMmNcdWM3NzRcdWIyOTQgXHVjNzA0XHVjZTU4IFx1Y2Q5NFx1YzgwMSBcdWM3YTVcdWNlNThcdWI5N2MgXHViOWNlXHVjNzc0IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVkNTg5XHViM2Q5XHVjNzQ0ICRrJFx1YmM4OCBcdWQ1NzRcdWMxMWMgXHVjNWQwXHViOWFkXHVjNzc0IFx1YzIyOFx1YzViNFx1Yzc4OFx1YjI5NCBcdWFjNzRcdWJiM2NcdWM3NDQgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCAkayRcdWI5N2MgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzViNFx1YjVhNCBcdWMyMTggJHgkICQoMSBcXGxlcSB4IFxcbGVxIE4pJFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NzRcdWMxMWMgXHViOWFjXHViYWE4XHVjZWU4XHVjNWQwIFx1Yzc4NVx1YjgyNVx1ZDU1YyBcdWQ2YzQsIFx1YjlhY1x1YmFhOFx1Y2VlOFx1YzVkMCBcdWI3NDRcdWM2Y2NcdWM5YzBcdWIyOTQgXHVjMjE4XHViOTdjIFx1ZDY1NVx1Yzc3OFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWIyZTgsIFx1YmJmY1x1Y2MyY1x1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGMgXHVkNTg5XHViM2Q5XHVjNzQ0IFx1YWNiMFx1YzgxNVx1ZDU2MCBcdWI1NGMsIFx1YWRmOCBcdWM4MDQgXHVkNTg5XHViM2Q5XHViNGU0XHVjNWQwXHVjMTFjIFx1YzViYlx1Yzc0MCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JGkrMSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggJEFfaSRcdWM2NDAgJEJfaSRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlcSBpIFxcbGVxIE4tMSkkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNWQwXHViOWFkXHVjNzc0IFx1YzIyOFx1YzViNFx1Yzc4OFx1YjI5NCBcdWFjNzRcdWJiM2NcdWM3NDQgXHVjNTRjXHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWM3NTggJGskXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDIgXFxsZXEgTiBcXGxlcSAyMDAwJDxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlcSBBX2kgJmx0OyBCX2kgXFxsZXEgTiQgJCgxIFxcbGVxIGkgXFxsZXEgTi0xKSQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEgaSAmbHQ7IGogXFxsZXEgTiRcdWM3NzggXHViYWE4XHViNGUwICRpJCwgJGokXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyAkaSRcdWJjODggXHVhYzc0XHViYjNjXHVhY2ZjICRqJFx1YmM4OCBcdWFjNzRcdWJiM2NcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM4NzRcdWM3YWM8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+JEFfaSA9IDEkICQoMSBcXGxlcSBpIFxcbGVxIE4tMSkkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kTiBcXGxlcSAxMDAkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5cdWNkOTRcdWFjMDAgXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NCBcdWM1YzZcdWM3NGM8XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+XHViOWFjXHViYWE4XHVjZWU4XHVjNWQwICQyJFx1YmM4OFx1Yzc0NCBcdWM3ODVcdWI4MjVcdWQ1NzRcdWMxMWMgXHVkNTVjIFx1YmM4OCBcdWI5Y2NcdWM1ZDAgXHVjNWQwXHViOWFkXHVjNzc0IFx1YzIyOFx1YzViNFx1Yzc4OFx1YjI5NCBcdWFjNzRcdWJiM2NcdWM3NDQgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjkyMDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIaWRlIGFuZCBTZWVrIGluIEtTQSIsImRlc2NyaXB0aW9uIjoiPHA+SW4gS1NBLCB0aGVyZSBhcmUgYnVpbGRpbmdzIG51bWJlcmVkIGZyb20gJDEkIHRvICROJCwgYW5kIHRoZXJlIGFyZSAkTi0xJCBjb3JyaWRvcnMgY29ubmVjdGluZyB0aGUgYnVpbGRpbmdzIGluIGJvdGggZGlyZWN0aW9ucy4gQ29ycmlkb3IgJGkkIGNvbm5lY3RzIGJ1aWxkaW5nICRBX2kkIGFuZCBidWlsZGluZyAkQl9pJC4sIGFuZCB0aGVyZSZuYnNwO2Fsd2F5cyBleGlzdHMmbmJzcDthIHBhdGggZnJvbSBhbnkgYnVpbGRpbmcgdG8gYW55IG90aGVyIGJ1aWxkaW5nLiBNaW5jaGFuIGFuZCBFcmljIGFyZSBwbGF5aW5nIGhpZGUgYW5kIHNlZWsgaGVyZS4gTWluY2hhbiBpcyB0aGUgc2Vla2VyIGFuZCBuZWVkcyB0byBmaW5kIEVyaWMsIHdobyBpcyBoaWRpbmcgaW4gb25lIG9mIHRoZSBidWlsZGluZ3MgbnVtYmVyZWQgZnJvbSAkMSQgdG8gJE4kLjxcL3A+XHJcblxyXG48cD5NaW5jaGFuIHdhbnRzIHRvIHdpbiB0aGUgZ2FtZSB3aXRoIHRoZSBoZWxwIG9mJm5ic3A7bG9jYXRpb24gdHJhY2tpbmcgZGV2aWNlIHdoaWNoIHdhcyBzZWNyZXRseSBoaWRkZW4gb24gRXJpYyYjMzk7cyBjbG90aGVzLiBUaGlzIHRyYWNraW5nIGRldmljZSBvbmx5IHJldmVhbHMgdGhlIGxvY2F0aW9uIGluIHRoZSBmb2xsb3dpbmcgd2F5OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPklmIHlvdSBpbnB1dCBhbiBpbnRlZ2VyICR4JCAkKDEgXFxsZSB4IFxcbGUgTikkIG9uIHRoZSByZW1vdGUgY29udHJvbCBvZiB0aGUgdHJhY2tpbmcgZGV2aWNlLCBpdCB3aWxsIGRpc3BsYXkgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGNvcnJpZG9ycyB0aGF0IG5lZWQgdG8gYmUgcGFzc2VkIHRvIHJlYWNoIHRoZSBidWlsZGluZyB3aGVyZSBFcmljIGlzIGhpZGluZyZuYnNwO2Zyb20gYnVpbGRpbmcgJHgkLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlNpbmNlIHRoZSBiYXR0ZXJ5IG9mIHRoZSB0cmFja2luZyBkZXZpY2UgaXMgcnVubmluZyBsb3csIE1pbmNoYW4gY2Fubm90IHVzZSBpdCB0b28gbWFueSB0aW1lcy4gUGxlYXNlIGZpbmQgdGhlIHNtYWxsZXN0IGludGVnZXIgJGskLCBzbyB0aGF0IE1pbmNoYW4gY2FuIHNlY3VyZSB0aGUgbnVtYmVyIG9mIHRoZSBidWlsZGluZyB3aGVyZSBFcmljIGlzIGhpZGluZyBpbiB1c2luZyAkayQgb3BlcmF0aW9ucyBvZiB0aGUgZm9sbG93aW5nIGtpbmQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+U2VsZWN0IGFuIGludGVnZXIgJHgkICQoMSBcXGxlIHggXFxsZSBOKSQsIGFuZCBmaW5kIG91dCB0aGUgbnVtYmVyIG91dHB1dCBieSB0aGUgdHJhY2tpbmcgZGV2aWNlLCB3aGVuIHRoZSBpbnRlZ2VyJm5ic3A7JHgkIGlzIHRoZSBpbnB1dCB0byB0aGUgcmVtb3RlIGNvbnRyb2wuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Tm90ZSB0aGF0IHVwb24gZGVjaWRpbmcgb24gdGhlIG5leHQgb3BlcmF0aW9uLCBNaW5jaGFuIGNhbiB1c2UgdGhlIGluZm9ybWF0aW9uIGFjcXVpcmVkIGZyb20gdGhlIHByZXZpb3VzIG9wZXJhdGlvbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyJm5ic3A7JE4kLjxcL3A+XHJcblxyXG48cD5UaGUgJGkrMSQtdGggbGluZSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICRBX2kkIGFuZCAkQl9pJC4gJCgxIFxcbGVxIGkgXFxsZXEgTi0xKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgc21hbGxlc3QgaW50ZWdlciAkayQgdG8gc2VjdXJlIHRoZSBudW1iZXIgb2YgdGhlIGJ1aWxkaW5nIHdoZXJlIEVyaWMgaXMgaGlkaW5nIGluLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDIgXFxsZXEgTiBcXGxlcSAyMDAwJDxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlcSBBX2kgJmx0OyBCX2kgXFxsZXEgTiQgJCgxIFxcbGVxIGkgXFxsZXEgTi0xKSQ8XC9saT5cclxuXHQ8bGk+Rm9yIGFsbCAkaSQsICRqJCBzYXRpc2Z5aW5nICQxIFxcbGVxIGkgJmx0OyZuYnNwO2ogXFxsZXEgTiQsIGEgcGF0aCBjb25uZWN0aW5nJm5ic3A7YnVpbGRpbmcgJGkkIGFuZCZuYnNwO2J1aWxkaW5nICRqJCZuYnNwO2V4aXN0czxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kQV9pID0gMSQgJCgxIFxcbGVxIGkgXFxsZXEgTi0xKSQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiROIFxcbGVxIDEwMCQ8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPk5vIGFkZGl0aW9uYWwgY29uc3RyYWludHM8XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+QnkgaW5wdXR0aW5nIHRoZSBudW1iZXIgJDIkIG9uIHRoZSByZW1vdGUgY29udHJvbCwgeW91IGNhbiBpbW1lZGlhdGVseSBrbm93IHRoZSBidWlsZGluZyB3aGVyZSBFcmljIGlzIGhpZGluZyBpbi48XC9wPlxyXG4ifV0=