60_1_Q2_1

def next_boards(board):
# ตัวอยาง board = (0,1,3,4,2,6,7,5,8)
# ผลที่ได[ ((1,0,3,4,2,6,7,5,8),'R'), ((4,1,3,0,2,6,7,5,8),'D') ]
    results = list()
    ind=board.index(0)
    if ind//3 !=0:
        res=list(board)
        res[ind],res[ind-3]=res[ind-3],res[ind]
        results.append((tuple(res),'U'))
    if ind%3 !=0:
        res=list(board)
        res[ind],res[ind-1]=res[ind-1],res[ind]
        results.append((tuple(res),'L'))
    if ind//3 !=2:
        res=list(board)
        res[ind],res[ind+3]=res[ind+3],res[ind]
        results.append((tuple(res),'D'))
    if ind%3 !=2:
        res=list(board)
        res[ind],res[ind+1]=res[ind+1],res[ind]
        results.append((tuple(res),'R'))

    return sorted(results) # ตอง sort ใหเปนระเบียบ
command = input().strip()
start_board = tuple([int(c) for c in list(input().strip())])
if command == '1':
    print(next_boards(start_board))
elif command == '2':
    pendings = [ (start_board , "") ]
    while len(pendings) > 0:
        (current_board , moves) = pendings.pop(0)
# (current_board,moves) = ( (0,1,3,4,2,6,7,5,8), 'LU' )
        if current_board == (1,2,3,4,5,6,7,8,0):
            print(moves)
            break
        results = next_boards(current_board)
# results = [ ((1,0,3,4,2,6,7,5,8),'R'), ((4,1,3,0,2,6,7,5,8),'D') ]
        new_boards_and_moves = [(b,moves+direction) for (b,direction) in results]
# new_boards_and_moves = [((1,0,3,4,2,6,7,5,8),'LUR'), ((4,1,3,0,2,6,7,5,8),'LUD')]
# นำแตละ tuple ใน new_boards_and_moves ไปตอทาย pendings
# pendings = [ เก็บ tuples มากมาย ]
        for e in new_boards_and_moves:
            pendings.append(e)
# pendings = [ เก็บ tuples มากมาย , ((1,0,3,4,2,6,7,5,8),'LUR'), ((4,1,3,0,2,6,7,5,8),
# 'LUD')]