Non-attacking Tanks

On an \(n \times n\) chessboard, there are \(n\) tanks. Each tank can attack every cell in its own row and column. Initially, the tanks are positioned arbitrarily, and a young player is enjoying his own version of \(\text{World War II}\) until his mother calls him to have dinner. Unwilling to stop playing, he decides to move the tanks.

In one move, you can choose any one tank and shift it one cell in one of the four directions: up, down, left, or right. Your task is to find the minimum number of moves required to obtain a configuration in which no two tanks can attack each other, that is, no two tanks share the same row or the same column. In addition, you must output one corresponding arrangement (plan) of tanks that achieves this minimum number of moves.

Note: The tanks cannot move outside the board.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)), representing the size of the board and the number of tanks.

The following \(n\) lines each contain two integers \(r_i\) and \(c_i\) (\(1 \le r_i, c_i \le n\)), representing the initial row and column of the \(i\)-th tank.

outputFormat

On the first line, output a single integer representing the minimum total number of moves required.

Then output \(n\) lines. The \(i\)-th of these lines should contain two integers \(r'_i\) and \(c'_i\), representing the final row and column for the \(i\)-th tank in the same order as the input. This final configuration must satisfy that all \(r'_i\) are distinct and all \(c'_i\) are distinct.

sample

1
1 1

0
1 1