34885번 - 파티로 가는 길 투 스텝

문제

이 문제는 투 스텝 문제입니다.

찬우는 ALOHA 파티에 초대받았다. 찬우는 술과 고기를 매우 좋아하기 때문에, 파티에 최대한 빠르게 도착하여 술과 고기를 전부 먹어 치우려고 한다!

하지만 찬우는 파티로 가는 길을 알지 못하기 때문에 파티로 가는 길을 알고 있는 당신에게 도움을 요청하였다.

당신은 찬우의 집이 $(1,1)$ 위치에, 파티장이 $(N,M)$ 위치에 있는 $N \times M$ 크기의 격자 모양 지도 $A$를 가지고 있으며, 위치 $(i,j)$가 이동할 수 있는 격자라면 .으로, 이동할 수 없는 격자라면 #으로 표현되어 있다.

찬우는 격자 모양 지도에서 상하좌우로 인접한 4ドル$개의 칸으로 이동할 수 있다. 지도의 밖이나 #로는 이동할 수 없다.

어떤 경로의 거리를 시작 위치에서 끝 위치까지 이동하는 과정에서 상하좌우로 이동한 횟수로 정의한다.

찬우의 집에서부터 파티장까지 최단 경로의 거리가 $D$라고 할 때, 당신은 찬우에게 정점 3ドルD$개의 루트가 있는 트리 하나를 줄 수 있다. 찬우를 도와주자.

입력

당신의 프로그램은 채점 데이터 하나당 총 두 번 실행된다. 당신은 하나의 소스 코드에 두 가지 실행 과정을 모두 구현해야 한다.

모든 입력의 첫 줄에는 실행 단계를 나타내는 정수 $T$가 주어진다. $(1 \leq T \leq 2)$

만약 $T$가 1ドル$이라면 첫 번째 단계를 수행해야 하고, $T$가 2ドル$라면 두 번째 단계를 수행해야 한다.

출력

제한

첫 번째 단계

첫 번째 단계에서는 지도를 보고 찬우에게 줄 트리를 출력해야 한다.

입력

둘째 줄에 지도의 높이 $N$과 너비 $M$이 공백으로 구분되어 주어진다. $(2 \leq N, M \leq 100)$

셋째 줄부터 $N$개의 줄에 걸쳐 $i+2$번째 줄에 지도 $A_{i,1}, A_{i,2}, \ldots, A_{i,M}$가 공백 구분 없이 주어진다.

$A_{1,1}$과 $A_{N,M}$은 항상 .임이 보장되며, 항상 $(1,1)$에서 $(N,M)$까지의 경로가 있는 입력만 주어진다.

출력

첫째 줄에 찬우의 집에서부터 파티장까지의 최단 거리 $D$를 출력한다.

이후 3ドルD-1$개의 줄에 걸쳐 $i+1$번째 줄에 트리의 $i$번째 간선이 연결하는 두 정점 $u_i, v_i$를 공백으로 구분하여 출력한다. (1ドル \le u_i, v_i \le 3D$)

출력은 정점 3ドルD$의 트리여야 한다.

당신이 출력한 트리의 루트는 1ドル$로 고정된다.

두 번째 단계

두 번째 단계에서는 찬우가 집에서 파티장으로 이동해야 한다.

입력

첫째 줄에 최단 거리 $D$가 주어진다.

이후 3ドルD-1$개의 줄에 걸쳐 당신이 첫 번째 단계에 출력한 트리가 주어진다. 트리의 간선의 순서는 출력한 순서와 상관없이 섞이게 되고, 트리의 정점의 번호 또한 1ドル$번 정점을 제외하고 번호가 뒤섞이게 된다.

$i+1$번째 줄에 트리의 $i$번째 간선이 연결하는 두 정점 $u_i, v_i$가 공백으로 구분되어 주어진다. (1ドル \le u_i, v_i \le 3D$)

출력

첫째 줄에 찬우의 집부터 파티장까지의 이동 방법을 U, D, L, R중 하나의 문자로 표현한 길이 $D$의 문자열을 출력한다.

찬우가 $i$번째 이동 전에 있는 위치를 $(x,y)$라고 정의하자.

• 만약 $i$번째 문자가 U라면, 찬우는 $i$번째 이동에서 $(x-1,y)$로 이동한다.
• 만약 $i$번째 문자가 D라면, 찬우는 $i$번째 이동에서 $(x+1,y)$로 이동한다.
• 만약 $i$번째 문자가 L라면, 찬우는 $i$번째 이동에서 $(x,y-1)$로 이동한다.
• 만약 $i$번째 문자가 R라면, 찬우는 $i$번째 이동에서 $(x,y+1)$로 이동한다.

찬우는 $(1,1)$에서 시작하며, $D$회 이동을 마친 후 $(N,M)$에 도달해야 한다.

만약 가능한 경로가 여러 가지라면, 아무 경로로 이동해도 상관 없다.

노트