소 빨래줄 정리

소들이 빨래를 말리려고 전선 $N$개($1 \le N \le 1000$)가 달린 빨랫줄을 세웠다. 소는 엄지손가락이 마주 보지 않아서 작업에 실패했고, 그 결과 전선들이 서로 꼬였다. 전선이 4개인 빨랫줄의 예는 다음과 같다.

   Wire slot: 1   2    3    4
              ---------------   <-- the holder of the wires
              \    \  /    /
               \    \/    /
                \   /\   /       
                 \ /  \ /       <-- actual clothes lines
                  /    \
                 / \  / \
                /   \/   \
               /    /\    \
              /    /  \    \
              ---------------   <-- the holder of the wires
   Wire slot: 1   2    3    4

전선이 꼬여 있다. 이대로는 쓸 수 없다.

소들은 최소한의 노력으로 빨랫줄을 풀고 싶어 한다. 팔이 짧아서 위쪽이나 아래쪽 고정대에서 인접한 두 전선 끝을 맞바꾸는 연산만 할 수 있다. 위 그림의 경우 이런 교환을 4번 하면 올바른 배치가 된다.

              1   2   3   4
              -------------   <-- the holder of the wires
              |   |   |   |
              |   |   |   |
              |   |   |   |
              |   |   |   |
              |   |   |   |
              |   |   |   |
              |   |   |   |
              |   |   |   |
              |   |   |   |
              -------------   <-- the holder of the wires
              1   2   3   4

빨랫줄을 바르게 정리하는 데 필요한 인접 교환 횟수의 최솟값을 구하라.

첫 줄에 정수 $N$이 주어진다. 이어지는 $N$개의 줄에는 각각 1부터 $N$까지의 정수 두 개가 주어진다. 첫 번째 정수는 위쪽 고정대에 있는 전선 번호이고, 두 번째 정수는 같은 칸의 아래쪽 고정대에 있는 전선 번호이다. 둘째 줄은 위쪽 1번 칸과 아래쪽 1번 칸, 셋째 줄은 위쪽 2번 칸과 아래쪽 2번 칸을 나타낸다.

인접한 전선을 교환하는 최소 횟수를 정수 하나로 출력한다.

위쪽의 3번 전선을 왼쪽으로 한 칸 옮기고, 다시 왼쪽으로 한 칸 옮긴다. 4번 전선도 같은 방법으로 옮긴다.