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

문제

하나의 큰 원에 1부터 N까지 숫자가 적힌 점이 시계방향으로 차례로 있다. 그리고 각 점은 서로 다른 두 점과 연결이 되어있다. (즉, 모든 점의 차수는 2라는 뜻이다.)

그런데 이 점을 연결하는 과정에서 연결하는 선이 서로 엉켜있다면 이것은 볼록다각형이 되지 못할 것이다. 그래서 원 위에 있는 점을 적절한 곳으로 옮겨서 선이 서로 엉키는 것을 푸려고 한다. 다음 그림을 보자.

처음에 왼쪽 그림과 같이 연결이 되어 있다고 하자. 그리고 4번 점을 빨간색 화살표와 같이 이동하면 오른쪽과 같이 될 것이다. 오른쪽 그림은 서로 엉킨 것이 없어 볼록다각형이 될 것이다.

위의 그림도 마찬가지로 가장 왼쪽에 있는 상태에서 위의 빨간색 화살표를 따라 두 번의 이동을 하면 가장 오른쪽과 같이 서로 엉키는 부분이 없어지게 된다.

1부터 N번까지의 점이 연결된 상태들의 정보가 주어져 있을 때, 엉킨 것을 모두 풀어서 볼록 N각형이 되게 하려면 최소한 몇 번의 점의 이동이 있어야 하는지 구하는 프로그램을 작성하여라.

입력

첫째 줄에 점들의 개수 N(1≤N≤500)이 주어진다. 그리고 두 번째 줄부터 N+1번째 줄까지 점들의 연결 상태가 주어진다. 각 정보는 두 개의 정수로 이루어 져 있는데 i번째 줄에 a와 b 두 정수가 주어져 있다면 i번 점과 a, b가 연결이 되어 있다는 것을 의미한다.

출력

첫 줄에 최소 이동 회수를 출력한다. 만약에 볼록 N각형을 만드는 것이 불가능 한 경우에는 -1을 출력한다.

예제 입력 1

6
4 5
3 5
2 6
1 6
1 2
3 4

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjE4NDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZmNcdWI4NWRcdWIyZTRcdWFjMDFcdWQ2MTUgXHViOWNjXHViNGU0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NThcdWIwOThcdWM3NTggXHVkMDcwIFx1YzZkMFx1YzVkMCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzgwMVx1ZDc4YyBcdWM4MTBcdWM3NzQgXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFjMDEgXHVjODEwXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YzgxMFx1YWNmYyBcdWM1ZjBcdWFjYjBcdWM3NzQgXHViNDE4XHVjNWI0XHVjNzg4XHViMmU0LiAoXHVjOTg5LCBcdWJhYThcdWI0ZTAgXHVjODEwXHVjNzU4IFx1Y2MyOFx1YzIxOFx1YjI5NCAyXHViNzdjXHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4pPFwvcD48cD5cdWFkZjhcdWI3ZjBcdWIzNzAgXHVjNzc0IFx1YzgxMFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhY2ZjXHVjODE1XHVjNWQwXHVjMTFjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWMxMjBcdWM3NzQgXHVjMTFjXHViODVjIFx1YzVjOVx1Y2YxY1x1Yzc4OFx1YjJlNFx1YmE3NCBcdWM3NzRcdWFjODNcdWM3NDAgXHViY2ZjXHViODVkXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0IFx1YjQxOFx1YzljMCBcdWJhYmJcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNmQwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODEwXHVjNzQ0IFx1YzgwMVx1YzgwOFx1ZDU1YyBcdWFjZjNcdWM3M2NcdWI4NWMgXHVjNjJlXHVhY2E4XHVjMTFjIFx1YzEyMFx1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjNWM5XHVkMGE0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWQ0NzhcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWIyZTRcdWM3NGMgXHVhZGY4XHViOWJjXHVjNzQ0IFx1YmNmNFx1Yzc5MC48XC9wPlxyXG48cD48aW1nIHdpZHRoPVwiMjYzXCIgaGVpZ2h0PVwiMTMwXCIgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDdcL2JwLlBOR1wiIFwvPjxcL3A+XHJcbjxwPlx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWM3NzQgXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YWRmOFx1YjlhY1x1YWNlMCA0XHViYzg4IFx1YzgxMFx1Yzc0NCBcdWJlNjhcdWFjMDRcdWMwYzkgXHVkNjU0XHVjMGI0XHVkNDVjXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzQgXHVjNjI0XHViOTc4XHVjYWJkXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWI0MjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWM1YzlcdWQwYTggXHVhYzgzXHVjNzc0IFx1YzVjNlx1YzViNCBcdWJjZmNcdWI4NWRcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzQgXHViNDIwIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD48aW1nIHdpZHRoPVwiMjc2XCIgaGVpZ2h0PVwiMTA4XCIgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDdcL2JwMi5QTkdcIiBcLz48XC9wPlxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHViM2M0IFx1YjljOFx1Y2MyY1x1YWMwMFx1YzljMFx1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWQwZGNcdWM1ZDBcdWMxMWMgXHVjNzA0XHVjNzU4IFx1YmU2OFx1YWMwNFx1YzBjOSBcdWQ2NTRcdWMwYjRcdWQ0NWNcdWI5N2MgXHViNTMwXHViNzdjIFx1YjQ1MCBcdWJjODhcdWM3NTggXHVjNzc0XHViM2Q5XHVjNzQ0IFx1ZDU1OFx1YmE3NCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjNWM5XHVkMGE0XHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc3NCBcdWM1YzZcdWM1YjRcdWM5YzBcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcbjxwPjFcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjNWYwXHVhY2IwXHViNDFjIFx1YzBjMVx1ZDBkY1x1YjRlNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODM4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YzVjOVx1ZDBhOCBcdWFjODNcdWM3NDQgXHViYWE4XHViNDUwIFx1ZDQ4MFx1YzViNFx1YzExYyBcdWJjZmNcdWI4NWQgTlx1YWMwMVx1ZDYxNVx1Yzc3NCBcdWI0MThcdWFjOGMgXHVkNTU4XHViODI0XHViYTc0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1YyBcdWJhODcgXHViYzg4XHVjNzU4IFx1YzgxMFx1Yzc1OCBcdWM3NzRcdWIzZDlcdWM3NzQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTBcdWI0ZTRcdWM3NTggXHVhYzFjXHVjMjE4IE4oMSZsZTtOJmxlOzUwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWM4MTBcdWI0ZTRcdWM3NTggXHVjNWYwXHVhY2IwIFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM4MTVcdWJjZjRcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0IFx1YzgzOCBcdWM3ODhcdWIyOTRcdWIzNzAgaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgYVx1YzY0MCBiIFx1YjQ1MCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNFx1YmE3NCBpXHViYzg4IFx1YzgxMFx1YWNmYyBhLCBiXHVhYzAwIFx1YzVmMFx1YWNiMFx1Yzc3NCBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YzE4YyBcdWM3NzRcdWIzZDkgXHVkNjhjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkXHVjNWQwIFx1YmNmY1x1Yjg1ZCBOXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NzQgXHViZDg4XHVhYzAwXHViMmE1IFx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxODQ3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSHVtYW4gS25vdCIsImRlc2NyaXB0aW9uIjoiPHA+QSBjbGFzc2ljIGljZSZtaW51czticmVha2luZyBleGVyY2lzZSBpcyBmb3IgYSBncm91cCBvZiBuIHBlb3BsZSB0byBmb3JtIGEgY2lyY2xlIGFuZCB0aGVuIGFyYml0cmFyaWx5IGpvaW4gaGFuZHMgd2l0aCBvbmUgYW5vdGhlci4gVGhpcyBmb3JtcyBhICZxdW90O2h1bWFuIGtub3QmcXVvdDsgc2luY2UgdGhlIHBsYXllcnMmIzM5OyBhcm1zIGFyZSBtb3N0IGxpa2VseSBpbnRlcnR3aW5lZC4gVGhlIGdvYWwgaXMgdGhlbiB0byB1bndpbmQgdGhlIGtub3QgdG8gZm9ybSBhIGNpcmNsZSBvZiBwbGF5ZXJzIHdpdGggbm8gYXJtcyBjcm9zc2VkLjxcL3A+XHJcblxyXG48cD5XZSBub3cgYWRhcHQgdGhpcyBnYW1lIHRvIGEgbW9yZSBnZW5lcmFsIGFuZCBtb3JlIGFic3RyYWN0IHNldHRpbmcgd2hlcmUgdGhlIHBoeXNpY2FsIGNvbnN0cmFpbnRzIG9mIHRoZSBwcm9ibGVtIGFyZSBnb25lLiBTdXBwb3NlIHdlIHJlcHJlc2VudCB0aGUgaW5pdGlhbCBrbm90IHdpdGggYSAyJm1pbnVzO3JlZ3VsYXIgZ3JhcGggaW5zY3JpYmVkIGluIGEgY2lyY2xlIChpLmUuLCB3ZSBoYXZlIGEgZ3JhcGggd2l0aCBuIHZlcnRpY2VzIHdpdGggZXhhY3RseSB0d28gZWRnZXMgaW5jaWRlbnQgb24gZWFjaCB2ZXJ0ZXgpLiBJbml0aWFsbHksIHNvbWUgZWRnZXMgbWF5IGNyb3NzIG90aGVyIGVkZ2VzIGFuZCB0aGlzIGlzIHVuZGVzaXJhYmxlLiBUaGlzIGlzIHRoZSAmcXVvdDtrbm90JnF1b3Q7IHdlIHdpc2ggdG8gdW53aW5kLjxcL3A+XHJcblxyXG48cD5BICZxdW90O21vdmUmcXVvdDsgaW52b2x2ZXMgbW92aW5nIGFueSB2ZXJ0ZXggdG8gYSBuZXcgcG9zaXRpb24gb24gdGhlIGNpcmNsZSwga2VlcGluZyBpdHMgZWRnZXMgaW50YWN0LiBPdXIgZ29hbCBpcyB0byBtYWtlIHRoZSBmZXdlc3QgcG9zc2libGUgbW92ZXMgc3VjaCB0aGF0IHdlIG9idGFpbiBvbmUgbiZtaW51cztzaWRlZCBwb2x5Z29uIHdpdGggbm8gZWRnZSZtaW51cztjcm9zc2luZ3MgcmVtYWluaW5nLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaGVyZSBpcyBhIGtub3Qgb24gNCB2ZXJ0aWNlcyBpbnNjcmliZWQgaW4gYSBjaXJjbGUsIGJ1dCB0d28gZWRnZXMgY3Jvc3MgZWFjaCBvdGhlci4gQnkgbW92aW5nIHZlcnRleCA0IGRvd24gdG8gdGhlIHBvc2l0aW9uIGJldHdlZW4gMiBhbmQgMywgYSBncmFwaCB3aXRob3V0IGVkZ2UmbWludXM7Y3Jvc3NpbmdzIGVtZXJnZXMuIFRoaXMgd2FzIGFjaGlldmVkIGluIGEgc2luZ2xlIG1vdmUsIHdoaWNoIGlzIGNsZWFybHkgb3B0aW1hbCBpbiB0aGlzIGNhc2UuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva25vdDEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTcxcHg7IHdpZHRoOjQwMnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldoZW4gbiBpcyBsYXJnZXIsIHRoaW5ncyBtYXkgbm90IGJlIHF1aXRlIGFzIGNsZWFyLiBCZWxvdyB3ZSBzZWUgYSBrbm90IG9uIDYgdmVydGljZXMuIFdlIG1pZ2h0IGNvbnNpZGVyIG1vdmluZyB2ZXJ0ZXggNCBiZXR3ZWVuIDUgYW5kIDYsIHRoZW4gdmVydGV4IDUgYmV0d2VlbiAxIGFuZCAyLCBhbmQgZmluYWxseSB2ZXJ0ZXggNiBiZXR3ZWVuIDMgYW5kIDQ7IHRoaXMgdW53aW5kcyB0aGUga25vdCBpbiAzIG1vdmVzLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tub3QyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5MHB4OyB3aWR0aDo3MzhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5CdXQgY2xlYXJseSB3ZSBjYW4gdW53aW5kIHRoZSBzYW1lIGtub3QgaW4gb25seSB0d28gbW92ZXM6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva25vdDMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTk3cHg7IHdpZHRoOjYwNXB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBudW1iZXIgb2YgY2FzZXMuIEVhY2ggY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aGUgaW50ZWdlciBuICgzICZsdDs9IG4gJmx0Oz0gNTAwKSwgZ2l2aW5nIHRoZSBudW1iZXIgb2YgdmVydGljZXMgb2YgdGhlIGdyYXBoLiBUaGUgdmVydGljZXMgYXJlIGxhYmVsbGVkIGNsb2Nrd2lzZSBmcm9tIDEgdG8gbi4gRWFjaCBvZiB0aGUgbmV4dCBuIGxpbmVzIGdpdmVzIGEgcGFpciBvZiBuZWlnaGJvcnMsIHdoZXJlIGxpbmUgaSAoMSAmbHQ7PSBpICZsdDs9IG4pIHNwZWNpZmllcyB0aGUgdHdvIHZlcnRpY2VzIGFkamFjZW50IHRvIHZlcnRleCBpLiBUaGUgaW5wdXQgaXMgdGVybWluYXRlZCBieSBuID0gMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBjYXNlLCBpZiB0aGVyZSBpcyBubyBzb2x1dGlvbiwgcHJpbnQgJnF1b3Q7Tm90IHNvbHZhYmxlLiZxdW90OyBvbiBhIGxpbmUgYnkgaXRzZWxmLiBJZiB0aGVyZSBpcyBhIHNvbHV0aW9uLCBwcmludCAmcXVvdDtLbm90IHNvbHZhYmxlLiZxdW90OyBvbiBhIGxpbmUgYnkgaXRzZWxmLCBmb2xsb3dlZCBieSB0aGUgbWluaW11bSBudW1iZXIgb2YgbW92ZXMgcmVxdWlyZWQgdG8gc29sdmUgdGhlIHByb2JsZW0sIG9uIGEgbGluZSBieSBpdHNlbGYuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=