시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 63 10 7 21.212%

문제

하나의 큰 원에 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+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTg0NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikh1bWFuIEtub3QiLCJkZXNjcmlwdGlvbiI6IjxwPkEgY2xhc3NpYyBpY2UmbWludXM7YnJlYWtpbmcgZXhlcmNpc2UgaXMgZm9yIGEgZ3JvdXAgb2YgbiBwZW9wbGUgdG8gZm9ybSBhIGNpcmNsZSBhbmQgdGhlbiBhcmJpdHJhcmlseSBqb2luIGhhbmRzIHdpdGggb25lIGFub3RoZXIuIFRoaXMgZm9ybXMgYSAmcXVvdDtodW1hbiBrbm90JnF1b3Q7IHNpbmNlIHRoZSBwbGF5ZXJzJiMzOTsgYXJtcyBhcmUgbW9zdCBsaWtlbHkgaW50ZXJ0d2luZWQuIFRoZSBnb2FsIGlzIHRoZW4gdG8gdW53aW5kIHRoZSBrbm90IHRvIGZvcm0gYSBjaXJjbGUgb2YgcGxheWVycyB3aXRoIG5vIGFybXMgY3Jvc3NlZC48XC9wPlxyXG5cclxuPHA+V2Ugbm93IGFkYXB0IHRoaXMgZ2FtZSB0byBhIG1vcmUgZ2VuZXJhbCBhbmQgbW9yZSBhYnN0cmFjdCBzZXR0aW5nIHdoZXJlIHRoZSBwaHlzaWNhbCBjb25zdHJhaW50cyBvZiB0aGUgcHJvYmxlbSBhcmUgZ29uZS4gU3VwcG9zZSB3ZSByZXByZXNlbnQgdGhlIGluaXRpYWwga25vdCB3aXRoIGEgMiZtaW51cztyZWd1bGFyIGdyYXBoIGluc2NyaWJlZCBpbiBhIGNpcmNsZSAoaS5lLiwgd2UgaGF2ZSBhIGdyYXBoIHdpdGggbiB2ZXJ0aWNlcyB3aXRoIGV4YWN0bHkgdHdvIGVkZ2VzIGluY2lkZW50IG9uIGVhY2ggdmVydGV4KS4gSW5pdGlhbGx5LCBzb21lIGVkZ2VzIG1heSBjcm9zcyBvdGhlciBlZGdlcyBhbmQgdGhpcyBpcyB1bmRlc2lyYWJsZS4gVGhpcyBpcyB0aGUgJnF1b3Q7a25vdCZxdW90OyB3ZSB3aXNoIHRvIHVud2luZC48XC9wPlxyXG5cclxuPHA+QSAmcXVvdDttb3ZlJnF1b3Q7IGludm9sdmVzIG1vdmluZyBhbnkgdmVydGV4IHRvIGEgbmV3IHBvc2l0aW9uIG9uIHRoZSBjaXJjbGUsIGtlZXBpbmcgaXRzIGVkZ2VzIGludGFjdC4gT3VyIGdvYWwgaXMgdG8gbWFrZSB0aGUgZmV3ZXN0IHBvc3NpYmxlIG1vdmVzIHN1Y2ggdGhhdCB3ZSBvYnRhaW4gb25lIG4mbWludXM7c2lkZWQgcG9seWdvbiB3aXRoIG5vIGVkZ2UmbWludXM7Y3Jvc3NpbmdzIHJlbWFpbmluZy48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGhlcmUgaXMgYSBrbm90IG9uIDQgdmVydGljZXMgaW5zY3JpYmVkIGluIGEgY2lyY2xlLCBidXQgdHdvIGVkZ2VzIGNyb3NzIGVhY2ggb3RoZXIuIEJ5IG1vdmluZyB2ZXJ0ZXggNCBkb3duIHRvIHRoZSBwb3NpdGlvbiBiZXR3ZWVuIDIgYW5kIDMsIGEgZ3JhcGggd2l0aG91dCBlZGdlJm1pbnVzO2Nyb3NzaW5ncyBlbWVyZ2VzLiBUaGlzIHdhcyBhY2hpZXZlZCBpbiBhIHNpbmdsZSBtb3ZlLCB3aGljaCBpcyBjbGVhcmx5IG9wdGltYWwgaW4gdGhpcyBjYXNlLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tub3QxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE3MXB4OyB3aWR0aDo0MDJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5XaGVuIG4gaXMgbGFyZ2VyLCB0aGluZ3MgbWF5IG5vdCBiZSBxdWl0ZSBhcyBjbGVhci4gQmVsb3cgd2Ugc2VlIGEga25vdCBvbiA2IHZlcnRpY2VzLiBXZSBtaWdodCBjb25zaWRlciBtb3ZpbmcgdmVydGV4IDQgYmV0d2VlbiA1IGFuZCA2LCB0aGVuIHZlcnRleCA1IGJldHdlZW4gMSBhbmQgMiwgYW5kIGZpbmFsbHkgdmVydGV4IDYgYmV0d2VlbiAzIGFuZCA0OyB0aGlzIHVud2luZHMgdGhlIGtub3QgaW4gMyBtb3Zlcy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9rbm90Mi5wbmdcIiBzdHlsZT1cImhlaWdodDoxOTBweDsgd2lkdGg6NzM4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QnV0IGNsZWFybHkgd2UgY2FuIHVud2luZCB0aGUgc2FtZSBrbm90IGluIG9ubHkgdHdvIG1vdmVzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tub3QzLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5N3B4OyB3aWR0aDo2MDVweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgbnVtYmVyIG9mIGNhc2VzLiBFYWNoIGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdGhlIGludGVnZXIgbiAoMyAmbHQ7PSBuICZsdDs9IDUwMCksIGdpdmluZyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIG9mIHRoZSBncmFwaC4gVGhlIHZlcnRpY2VzIGFyZSBsYWJlbGxlZCBjbG9ja3dpc2UgZnJvbSAxIHRvIG4uIEVhY2ggb2YgdGhlIG5leHQgbiBsaW5lcyBnaXZlcyBhIHBhaXIgb2YgbmVpZ2hib3JzLCB3aGVyZSBsaW5lIGkgKDEgJmx0Oz0gaSAmbHQ7PSBuKSBzcGVjaWZpZXMgdGhlIHR3byB2ZXJ0aWNlcyBhZGphY2VudCB0byB2ZXJ0ZXggaS4gVGhlIGlucHV0IGlzIHRlcm1pbmF0ZWQgYnkgbiA9IDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSwgaWYgdGhlcmUgaXMgbm8gc29sdXRpb24sIHByaW50ICZxdW90O05vdCBzb2x2YWJsZS4mcXVvdDsgb24gYSBsaW5lIGJ5IGl0c2VsZi4gSWYgdGhlcmUgaXMgYSBzb2x1dGlvbiwgcHJpbnQgJnF1b3Q7S25vdCBzb2x2YWJsZS4mcXVvdDsgb24gYSBsaW5lIGJ5IGl0c2VsZiwgZm9sbG93ZWQgYnkgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzIHJlcXVpcmVkIHRvIHNvbHZlIHRoZSBwcm9ibGVtLCBvbiBhIGxpbmUgYnkgaXRzZWxmLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==