Problem Description

On an $n \times n$ chessboard, there are $n$ tanks. Each tank can attack all squares in its own row and column.

At the beginning, a child is happily playing his own “World War II” game, but his mother suddenly calls him to dinner.

He is very reluctant to stop, and plans to move these tanks several times. Each time, he moves one tank by one square in any of the four directions: up, down, left, or right.

Now he wants you to solve: what is the minimum number of moves needed to make the $n$ tanks unable to attack each other? Of course, to avoid thinking and go eat quickly, you also need to output one corresponding plan.

Input Format

The first line contains an integer $n$, the side length of the board and also the number of tanks.

The next $n$ lines each contain two integers $r, c$, meaning that when his mother called him to dinner, this tank was at row $r$, column $c$.

Rows and columns are numbered from top to bottom and from left to right, using $1 \sim n$. At any time, no two tanks may be in the same position.

Output Format

The first line outputs an integer $k$, the minimum number of moves.

The next $k$ lines each output an integer first, indicating which tank will be moved this time, then output a character, one of L (left), R (right), U (up), D (down), indicating the direction of the move.

The correct move sequence may not be unique. Output any one. This problem uses SPJ.

5
1 1
1 2
1 3
1 4
1 5 

10
1 D
2 D
3 D
4 D
1 D
2 D
3 D
1 D
2 D
1 D

5
2 3
3 2
3 3
3 4
4 3 

8
1 R
1 R
2 U
2 U
4 D
4 D
5 L
5 L

6
1 1
1 2
2 1
5 6
6 5
6 6

8
2 R
2 D
3 D
3 R
4 U
4 L
5 L
5 U 

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $5 \le n \le 500$, $1 \le r, c \le n$.

Notes

Translated from COCI2006-2007 CONTEST #3 T4 TENKICI

Translated by ChatGPT 5