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

문제

정원을 정리하던 배상욱은 흉측할 정도로 난잡하게 자란 정원수 한 그루를 발견했다. 가지치기를 할 시기가 된 것이다.

정원수는 n개의 정점과 n-1개의 간선으로 구성된, 연결 그래프로 표현된다. 그래프 내의 정점은 정원수의 잎사귀라고 할 수 있으며, 각 간선은 정원수의 가지들이라고 생각하자.

상욱은 가지치기를 통해 정원수 내의 잎사귀 개수가 m이 되도록 만드는 것이다. 즉, 정원수를 나타내는 그래프 내에 m개의 정점만 남겨야 한다. 가지치기란, 정원수 그래프 내의 간선을 끊는 일이다. 특정한 간선을 끊어, 그래프가 두 부분으로 분리되면, 한 부분을 취하고 다른 부분은 버린다.

상욱은 그리 부지런한 사람이 아닌 관계로, 최소한의 가지치기를 이용해서 정원수를 정리하기를 바란다. 정원수의 모양이 주어지면, 어떻게 가지치기를 해야 최소한의 가위질로 작업을 마무리할 수 있을지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 n과 m이 주어진다. (1<=n<=150, 1<=m<=n) 이후 한 줄에 한 개씩, 정원수의 가지를 나타내는 정보가 주어진다. 이는 정원수 내의 잎사귀 번호 두 개로 이루어져 있으며, 두 잎사귀 사이를 연결하는 가지가 있다는 의미이다. 잎사귀 번호는 1이상 n이하의 정수이다.

출력

첫째 줄에, 최소한의 가지치기 횟수를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 1

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

예제 출력 1

2

힌트

예시의 경우, 1-4, 1-5 두 개의 간선을 제거하면 원하는 크기의 정원수를 얻을 수 있다.

W3sicHJvYmxlbV9pZCI6IjE3NzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWM2ZDAgXHVjODE1XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWM2ZDBcdWM3NDQgXHVjODE1XHViOWFjXHVkNTU4XHViMzU4IFx1YmMzMFx1YzBjMVx1YzZiMVx1Yzc0MCBcdWQ3NDlcdWNlMjFcdWQ1NjAgXHVjODE1XHViM2M0XHViODVjIFx1YjA5Y1x1YzdhMVx1ZDU1OFx1YWM4YyBcdWM3OTBcdWI3ODAgXHVjODE1XHVjNmQwXHVjMjE4IFx1ZDU1YyBcdWFkZjhcdWI4ZThcdWI5N2MgXHViYzFjXHVhY2FjXHVkNTg4XHViMmU0LiBcdWFjMDBcdWM5YzBcdWNlNThcdWFlMzBcdWI5N2MgXHVkNTYwIFx1YzJkY1x1YWUzMFx1YWMwMCBcdWI0MWMgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbjxwPlx1YzgxNVx1YzZkMFx1YzIxOFx1YjI5NCBuXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1YWNmYyBuLTFcdWFjMWNcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYywgXHVjNWYwXHVhY2IwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MWNcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1ZDUwNCBcdWIwYjRcdWM3NTggXHVjODE1XHVjODEwXHVjNzQwIFx1YzgxNVx1YzZkMFx1YzIxOFx1Yzc1OCBcdWM3OGVcdWMwYWNcdWFkYzBcdWI3N2NcdWFjZTAgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMSBcdWFjMDRcdWMxMjBcdWM3NDAgXHVjODE1XHVjNmQwXHVjMjE4XHVjNzU4IFx1YWMwMFx1YzljMFx1YjRlNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NThcdWM3OTAuPFwvcD5cclxuPHA+XHVjMGMxXHVjNmIxXHVjNzQwIFx1YWMwMFx1YzljMFx1Y2U1OFx1YWUzMFx1Yjk3YyBcdWQxYjVcdWQ1NzQgXHVjODE1XHVjNmQwXHVjMjE4IFx1YjBiNFx1Yzc1OCBcdWM3OGVcdWMwYWNcdWFkYzAgXHVhYzFjXHVjMjE4XHVhYzAwIG1cdWM3NzQgXHViNDE4XHViM2M0XHViODVkIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgXHVjODE1XHVjNmQwXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWFkZjhcdWI3OThcdWQ1MDQgXHViMGI0XHVjNWQwIG1cdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHViOWNjIFx1YjBhOFx1YWNhOFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWMwMFx1YzljMFx1Y2U1OFx1YWUzMFx1Yjc4MCwgXHVjODE1XHVjNmQwXHVjMjE4IFx1YWRmOFx1Yjc5OFx1ZDUwNCBcdWIwYjRcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YjA0YVx1YjI5NCBcdWM3N2NcdWM3NzRcdWIyZTQuIFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWFjMDRcdWMxMjBcdWM3NDQgXHViMDRhXHVjNWI0LCBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHViNDUwIFx1YmQ4MFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWJkODRcdWI5YWNcdWI0MThcdWJhNzQsIFx1ZDU1YyBcdWJkODBcdWJkODRcdWM3NDQgXHVjZGU4XHVkNTU4XHVhY2UwIFx1YjJlNFx1Yjk3OCBcdWJkODBcdWJkODRcdWM3NDAgXHViYzg0XHViOWIwXHViMmU0LjxcL3A+XHJcbjxwPlx1YzBjMVx1YzZiMVx1Yzc0MCBcdWFkZjhcdWI5YWMgXHViZDgwXHVjOWMwXHViN2YwXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVhZDAwXHVhY2M0XHViODVjLCBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3NTggXHVhYzAwXHVjOWMwXHVjZTU4XHVhZTMwXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM4MTVcdWM2ZDBcdWMyMThcdWI5N2MgXHVjODE1XHViOWFjXHVkNTU4XHVhZTMwXHViOTdjIFx1YmMxNFx1Yjc4MFx1YjJlNC4gXHVjODE1XHVjNmQwXHVjMjE4XHVjNzU4IFx1YmFhOFx1YzU5MVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQsIFx1YzViNFx1YjViYlx1YWM4YyBcdWFjMDBcdWM5YzBcdWNlNThcdWFlMzBcdWI5N2MgXHVkNTc0XHVjNTdjIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWFjMDBcdWM3MDRcdWM5YzhcdWI4NWMgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjljOFx1YmIzNFx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVjOWMwIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG5cdWFjZmMgbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxJmx0Oz1uJmx0Oz0xNTAsIDEmbHQ7PW0mbHQ7PW4pIFx1Yzc3NFx1ZDZjNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1YyBcdWFjMWNcdWM1MjksIFx1YzgxNVx1YzZkMFx1YzIxOFx1Yzc1OCBcdWFjMDBcdWM5YzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBcdWM4MTVcdWM2ZDBcdWMyMTggXHViMGI0XHVjNzU4IFx1Yzc4ZVx1YzBhY1x1YWRjMCBcdWJjODhcdWQ2MzggXHViNDUwIFx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWI0NTAgXHVjNzhlXHVjMGFjXHVhZGMwIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuIFx1Yzc4ZVx1YzBhY1x1YWRjMCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1Yzc3NFx1YzBjMSBuXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAsIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWFjMDBcdWM5YzBcdWNlNThcdWFlMzAgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiPHA+XHVjNjA4XHVjMmRjXHVjNzU4IFx1YWNiZFx1YzZiMCwgMS00LCAxLTUgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTU4XHViYTc0IFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWQwNmNcdWFlMzBcdWM3NTggXHVjODE1XHVjNmQwXHVjMjE4XHViOTdjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+Iiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxNzcyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmVidWlsZGluZyBSb2FkcyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGNvd3MgaGF2ZSByZWNvbnN0cnVjdGVkIEZhcm1lciBKb2huJiMzOTtzIGZhcm0sIHdpdGggaXRzIE4gYmFybnMgKDEgJmx0Oz0gTiAmbHQ7PSAxNTAsIG51bWJlciAxLi5OKSBhZnRlciB0aGUgdGVycmlibGUgZWFydGhxdWFrZSBsYXN0IE1heS4gVGhlIGNvd3MgZGlkbiYjMzk7dCBoYXZlIHRpbWUgdG8gcmVidWlsZCBhbnkgZXh0cmEgcm9hZHMsIHNvIG5vdyB0aGVyZSBpcyBleGFjdGx5IG9uZSB3YXkgdG8gZ2V0IGZyb20gYW55IGdpdmVuIGJhcm4gdG8gYW55IG90aGVyIGJhcm4uIFRodXMsIHRoZSBmYXJtIHRyYW5zcG9ydGF0aW9uIHN5c3RlbSBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSB0cmVlLjxcL3A+XHJcblxyXG48cD5GYXJtZXIgSm9obiB3YW50cyB0byBrbm93IGhvdyBtdWNoIGRhbWFnZSBhbm90aGVyIGVhcnRocXVha2UgY291bGQgZG8uIEhlIHdhbnRzIHRvIGtub3cgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHJvYWRzIHdob3NlIGRlc3RydWN0aW9uIHdvdWxkIGlzb2xhdGUgYSBzdWJ0cmVlIG9mIGV4YWN0bHkgUCAoMSAmbHQ7PSBQICZsdDs9IE4pIGJhcm5zIGZyb20gdGhlIHJlc3Qgb2YgdGhlIGJhcm5zLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFR3byBpbnRlZ2VycywgTiBhbmQgUDxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OOiBOLTEgbGluZXMsIGVhY2ggd2l0aCB0d28gaW50ZWdlcnMgSSBhbmQgSi4gTm9kZSBJIGlzIG5vZGUgSiYjMzk7cyBwYXJlbnQgaW4gdGhlIHRyZWUgb2Ygcm9hZHMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5BIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIGludGVnZXIgdGhhdCBpcyB0aGUgbWluaW11bSBudW1iZXIgb2Ygcm9hZHMgdGhhdCBuZWVkIHRvIGJlIGRlc3Ryb3llZCBmb3IgYSBzdWJ0cmVlIG9mIFAgbm9kZXMgdG8gYmUgaXNvbGF0ZWQuPFwvcD5cclxuIiwiaGludCI6IjxwPkEgc3VidHJlZSB3aXRoIG5vZGVzICgxLCAyLCAzLCA2LCA3LCA4KSB3aWxsIGJlY29tZSBpc29sYXRlZCBpZiByb2FkcyAxLTQgYW5kIDEtNSBhcmUgZGVzdHJveWVkLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==