Distance on Triangulation 2

뜨룹랜드는 정점이 $2N$개인 볼록다각형 모양의 왕국이다.

볼록다각형의 각 정점에는 집이 하나씩 있다. 집들은 시계 방향으로 1부터 $2N$까지 번호가 매겨져 있다.

다각형의 둘레를 따라 $2N$개의 양방향 도로가 지어져 있다. 즉 모든 $i(1 \leq i < 2N)$에 대해 $i$번 집과 $i + 1$번 집이 도로로 연결되어 있고, 1번 집과 $2N$번 집이 도로로 연결되어 있다.

뜨룹랜드에는 1번부터 $N$번까지 번호가 매겨진 $N$명의 사람들이 살고 있다. 각 사람은 정확히 2개의 집을 소유하고 있다. 즉 주인이 없는 집은 없다. $i$번 사람이 소유한 두 집의 번호를 $x\_i$, $y\_i$라 하자.

뜨룹랜드에 다음 조건을 만족하도록 정확히 $2N-3$개의 양방향 도로를 더 지으려고 한다.

• 도로는 서로 다른 두 집을 선분으로 연결해야 한다.
• 이미 지어져 있는 도로를 포함하여, 같은 쌍을 잇는 도로는 2개 이상 있을 수 없다.
• 두 도로는 양쪽 끝이 아닌 지점에서 교차할 수 없다.

$a$번 집에서 $b$번 집으로 갈 때 거쳐야 하는 최소 도로 개수를 $Dist(a, b)$라 할 때, 위 조건을 만족하면서 $\sum\_{i=1}^{N} {Dist(x\_i, y\_i)}$가 최소가 되도록 하는 도로 배치를 구하여라.

첫째 줄에 $N$($2 \leq N \leq 200\ 000$) 이 주어진다.

그 후 $N$개의 줄에 $i$번 사람이 소유한 두 집의 번호인 $x\_i$, $y\_i$가 공백을 사이에 두고 주어진다. ($1 \leq x\_i, y\_i \leq 2N$)

첫째 줄에 $\sum\_{i=1}^{N} {Dist(x\_i, y\_i)}$의 최솟값을 출력한다.

그 후 $2N-3$개의 줄에 새로 지을 도로가 잇는 두 집의 번호를 공백을 사이에 두고 출력한다.

가능한 배치가 여러 가지라면 아무것이나 출력해도 된다.

그림 B.1: 예제 1에 대해 정답으로 가능한 도로 배치 중 하나

$Dist(1, 3)$ = 1, $Dist(4, 6)$ = 1, $Dist(2, 5)$ = 3 이므로 합은 5이다. 합을 4 이하로 만들 수 없으므로 해당 배치를 출력한다.