COCI 2006/2007, Contest #3

Task TENKICI

Mirko found a collection of N toy tanks dating back to the Second World War on his grandfather's attic. He promptly called his friend Slavko to play with him. They made a battlefield – a wooden board consisting of squares in N rows and N columns.

Each tank can be moved to one of the four neighbouring squares in a single move. A tank can shoot at any square in the same row and column. The tank is said to be guarding the row and column it is in.

Additionally, no two tanks can be in the same square at any time.

After many hours of play and two previous attempts, Mirko's mom yelled at them to come down for lunch again, and they decided to rearrange the tanks so that each tank guards a different row and column (meaning also that each row and column contains only one tank).

However, they want to do this using the minimum number of moves.

Write a program that finds the minimum number of moves required to rearrange the tanks so that each row and each column contains a single tank, and one such shortest sequence of moves.

Input

The first line of input contains the integer N (5 ≤ N ≤ 500).

Each of the following N lines contains two integers R and C (1 ≤ R, S ≤ N), the row and column of a single tank at the moment of mom's call. No two tanks are on the same square.

Rows and columns are marked 1 through N, top-down and left-to-right.

Output

Output the minimum number of moves (call this number K) on the first line.

Each of the next K lines should contain the tank being moved and the direction it is moved in, separated by a single space.

Tanks are numbered 1 through N, in the order in which they are given in the input.

The direction can be one of four uppercase letters: 'L' for left, 'R' for right, 'U' for up and 'D' for down.

Note: The sequence need not be unique.

Scoring

If both the number K and the sequence of moves are correct, your program will score full points on the test case.

If your program outputs the correct number K and does not output the sequence of moves, or the sequence of moves is incorrect, you will get 60% of the points for that test case.

Sample Tests

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

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Jul 15, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)