17446번 - 옥상 정원 스페셜 저지

서울대학교 신공학관 옥상에는 대학원생들에게만 보이는 커다란 정원이 있다. 이 정원에는 아름다운 꽃들이 피어 있는 정사각형 모양의 화단들이 격자 모양으로 늘어서 있으며, 화단의 변들을 따라 산책로가 나 있다.

곧 이 정원을 못 보게 되는 평석이는 추억을 간직하기 위해 마지막으로 정원을 방문했다. 평석이는 정원의 산책로를 걸으며 주변 화단들의 사진을 찍었다. 한참 여유를 즐기고 돌아가려던 평석이는 절망적인 사실을 깨달았다. 졸업 기념으로 가려고 애지중지 모셔 놨던 해외 게임쇼 티켓이 없어진 것이다!

평석이는 티켓을 찾기 위해 자신이 걸었던 산책로를 되짚어 보려고 했지만, 곧 연구실로 돌아가야 하기 때문에 모든 길을 다시 가 볼 수는 없었다. 다행히 평석이의 카메라에는 아까 찍은 화단들의 사진이 남아 있었기에, 평석이는 이 화단들의 주변 길들만 먼저 확인해 보기로 했다. 평석이는 시간이 얼마 없으므로 자신이 사진을 찍은 화단들의 네 변에 해당하는 길들만 정확히 한 번씩 지나가 보고, 그렇지 않은 길은 지나가지 않으려고 한다. 또한, 한 방향으로만 걸으면 집중력이 떨어질 수 있으므로 화단의 한 변을 지날 때마다 이동 방향을 바꾸려고 한다.

평석이는 가로 방향의 길과 세로 방향의 길이 만나는 어느 지점에서든 출발할 수 있다. 평석이가 조건을 만족하며 티켓을 찾아다닐 수 있을지 확인해 보자.

첫 줄에 정원의 세로 방향으로 늘어서 있는 화단의 개수와 가로 방향으로 늘어서 있는 화단의 개수를 의미하는 정수 N과 M(1 ≤ N, M ≤ 500)이 주어진다.

다음 N개의 줄에 걸쳐 각 줄에 정원의 화단들을 나타내는 M글자의 문자열이 하나씩 주어진다. 문자열은 문자 #와 .로만 이루어져 있으며, #는 평석이가 사진을 찍은 화단, .는 그렇지 않은 화단을 의미한다.

평석이가 사진을 찍은 화단이 하나 이상 있음이 보장된다.

평석이가 조건을 만족하며 이동할 수 있다면 첫 줄에 YES를 출력한다.

다음 줄에 평석이의 경로를 나타내는 문자열을 출력한다. 문자열은 문자 L, R, U, D로만 이루어져 있어야 하며, 각각 평석이가 왼쪽, 오른쪽, 위, 아래 방향으로 화단 한 변의 길이만큼 걸어감을 의미한다.

조건을 만족하는 경로가 없다면 첫 줄에 NO를 출력한다.

첫 번째 예시의 경로는 다음과 같다.