볼록 다각형 만들기

원 위에 1부터 N까지 번호가 붙은 점이 시계방향으로 놓여 있다. 각 점은 서로 다른 두 점과 선분으로 연결되어 있으므로, 주어진 연결 관계는 모든 점의 차수가 2인 무방향 그래프를 이룬다.

이 선분들이 서로 교차하면 현재 배치는 볼록 N각형의 변 순서가 아니다. 한 번의 이동은 점 하나를 원 위의 다른 위치로 옮겨 원 위의 순서를 바꾸는 것이다. 연결 관계는 그대로 유지된다.

점들을 필요한 만큼 이동하여 연결된 선분들이 서로 교차하지 않는 볼록 N각형의 둘레가 되게 하려고 한다. 가능한 경우 필요한 최소 이동 횟수를 구하라.

첫째 줄에 점의 개수 N(1 <= N <= 500)이 주어진다.

이어서 i = 1, 2, ..., N에 대해 한 줄에 두 정수 a, b가 주어진다. 이는 i번 점이 a번 점과 b번 점에 연결되어 있음을 뜻한다.

볼록 N각형을 만들 수 있다면 필요한 최소 이동 횟수를 출력한다. 만들 수 없다면 -1을 출력한다.