구슬 탈출 3

직사각형 보드에 빨간 구슬과 파란 구슬이 하나씩 들어 있다. 보드를 기울여 빨간 구슬만 구멍으로 빼내는 것이 목표다.

보드의 세로 크기는 $N$, 가로 크기는 $M$이고 $1 \times 1$ 크기의 칸으로 나뉘어 있다. 가장 바깥 행과 열은 모두 막혀 있고, 구멍은 하나뿐이다. 구슬은 칸 하나를 가득 채우는 크기다.

구슬을 손으로 건드릴 수는 없고 보드를 기울여 중력으로 굴려야 한다. 기울이는 방향은 왼쪽, 오른쪽, 위쪽, 아래쪽 네 가지다. 한 번 기울이면 두 구슬이 동시에 움직이고, 더 이상 움직이지 못할 때까지 굴러간 뒤 멈춘다.

빨간 구슬이 구멍에 빠지면 성공이다. 파란 구슬이 구멍에 빠지면 실패이고, 한 번의 기울이기에서 두 구슬이 함께 빠져도 실패다. 두 구슬이 같은 칸에 동시에 있을 수는 없다.

보드의 상태가 주어지면 빨간 구슬을 구멍으로 빼내는 데 필요한 최소 기울이기 횟수와 그 방법을 구하는 프로그램을 작성하시오.

첫째 줄에 보드의 세로 크기 $N$과 가로 크기 $M$이 주어진다 ($3 \le N, M \le 10$). 다음 $N$개 줄에 보드의 모양을 나타내는 길이 $M$의 문자열이 주어진다. 문자열은 '.', '#', 'O', 'R', 'B'로 이루어진다. '.'은 빈 칸, '#'은 구슬이 지나갈 수 없는 벽이나 장애물, 'O'는 구멍, 'R'은 빨간 구슬, 'B'는 파란 구슬의 위치다.

보드의 가장자리는 모두 '#'이다. 구멍은 한 개이고, 빨간 구슬과 파란 구슬도 각각 한 개씩 주어진다.

첫째 줄에 빨간 구슬을 구멍으로 빼내는 최소 기울이기 횟수를 출력하고, 둘째 줄에 기울인 순서를 공백 없이 한 줄로 출력한다. 왼쪽으로 기울이기는 'L', 오른쪽은 'R', 위쪽은 'U', 아래쪽은 'D'로 적는다.

최소 횟수가 같은 방법이 여럿이면 그중 사전순으로 가장 앞서는 문자열을 출력한다. 네 글자의 순서는 알파벳 순서인 'D' < 'L' < 'R' < 'U'를 따른다.

10번 이하로 기울여서 빨간 구슬을 빼낼 수 없으면 첫째 줄에 -1만 출력한다.