문제
과학 실험 시간이다. 여러분에게 주어진 것은 엄청난 양의 전선들로 이루어진 회로이다. 그러나 여러분 중 한 명이 실험이 시작하기도 전에 큰 사고를 낼 뻔 했는데, 발에 전선이 걸려 넘어진 것이 바로 그것이다. 전선이 무진장 꼬여 있기 때문에 전선이 하나만 잘못 움직여도 회로 전체가 움직여 버릴 수도 있다. 안전한 실험을 위해서 과학 선생님은 전선을 정리하라고 하신다.
회로에서 가장 문제가 되는 부분은 아래와 같이 두 줄로 이루어진 전선 홀더에 엉켜 있는 전선들이다. 전선 홀더에는 1부터 N까지 차례로 번호가 매겨진 슬롯들이 있고, 각 슬롯에 전선이 연결된다. 여러분은 전선이 서로 교차하지 않도록 정리해야만 한다.
전선을 정리하기 위해 여러분은 홀더 하나를 선택해서, 그 중 인접한 두 전선을 빼서 서로 교환하는 방법을 사용할 수 있다. 단, 여기서 인접한 전선이란 위쪽 홀더 또는 아래쪽 홀더에서 슬롯 번호의 차이가 1인 전선들을 의미한다. 위 그림 1의 경우, 위쪽 홀더의 2-3을 교환하고, 아래쪽 홀더의 2-3을 교환한 뒤, 위쪽 홀더의 1-2와 3-4를 교환하면 전선을 교차하지 않도록 정리할 수 있다. 전선의 연결 상태가 주어지면, 전선을 모두 정리하고 재밌는 과학 실험을 시작하기 위해 필요한 최소 교환 횟수를 출력하는 프로그램을 만들자.
입력
첫 줄에 홀더의 크기 N(1≤N≤1,000)이 주어진다.
이후 N개의 줄에 걸쳐 각 전선의 연결 상태가 주어진다. 각 줄의 첫 번째 수는 그 전선이 연결된 위쪽 홀더의 번호, 두 번째 수는 아래쪽 홀더의 번호를 나타낸다.
출력
전선을 정리하기 위한 최소 교환 횟수를 출력한다.
예제
4
1 3
2 4
3 1
4 2
4
로그인해야 코드를 작성할 수 있어요.