볼록 다각형 만들기
시간 제한2초메모리 제한128 MB
원 위에 놓인 N개의 점을 잇는 2-정규 그래프가 주어질 때, 선분이 겹치지 않는 볼록 N각형이 되도록 옮겨야 하는 점의 최소 개수를 구하거나 불가능하면 -1을 출력합니다.
문제
원 위에 1부터 N까지 번호가 붙은 점이 시계방향으로 놓여 있다. 각 점은 서로 다른 두 점과 선분으로 연결되어 있으므로, 주어진 연결 관계는 모든 점의 차수가 2인 무방향 그래프를 이룬다.
이 선분들이 서로 교차하면 현재 배치는 볼록 N각형의 변 순서가 아니다. 한 번의 이동은 점 하나를 원 위의 다른 위치로 옮겨 원 위의 순서를 바꾸는 것이다. 연결 관계는 그대로 유지된다.
점들을 필요한 만큼 이동하여 연결된 선분들이 서로 교차하지 않는 볼록 N각형의 둘레가 되게 하려고 한다. 가능한 경우 필요한 최소 이동 횟수를 구하라.
입력
첫째 줄에 점의 개수 N(1 <= N <= 500)이 주어진다.
이어서 i = 1, 2, ..., N에 대해 한 줄에 두 정수 a, b가 주어진다. 이는 i번 점이 a번 점과 b번 점에 연결되어 있음을 뜻한다.
출력
볼록 N각형을 만들 수 있다면 필요한 최소 이동 횟수를 출력한다. 만들 수 없다면 -1을 출력한다.