8-Puzzle Minimum Moves

On a 3 × 3 board, there are 8 pieces numbered from 1 to 8 and one empty space denoted by 0. A tile adjacent to the empty space can be moved into that space. Given an initial board configuration and a fixed target configuration

\( 1\;2\;3 \; 8\;0\;4 \; 7\;6\;5 \)

find a sequence of moves of minimum length that transforms the initial configuration into the target configuration. Each move is one of the following: 'R' (move the empty space right), 'D' (down), 'L' (left), or 'U' (up). If the initial configuration is already the target configuration, output an empty string.

inputFormat

The input consists of a single line containing a 9-digit string representing the board configuration in row-major order. The digit 0 represents the empty space.

For example: 123840765

outputFormat

Output a string of characters where each character represents a move (R, D, L, U) that transforms the initial configuration into the target configuration in the minimum number of moves. If the initial configuration is already the target, output an empty string. If no solution exists, output -1.

sample

123804765