Graduations at UNAL are coming and due to the quarantine and to avoid crowds, each student was scheduled to go individually to pick up their diploma on the UNAL campus.
Today it's Vitor's time, he is dressed in a fancy suit and ready to go. Let's imagine the university as a grid of $N$ x $M$ cells, where the lower-left corner is $(1, 1)$ and the upper-right corner is $(N, M)$. Each cell has one of the following characters:
Vitor can walk only through clean cells and for each step he can go from one to another cell if they share a side. However, UNAL keeps some secrets, one of them is the existence of tunnels that can take him from one cell to another cell in one step and keep him clean, isn't that magical? More precisely, a clean cell $(x_1, y_1)$ is connected with another clean cell $(x_2, y_2)$ by a tunnel if and only if the following conditions are met:
Vitor wants to reach his destination as soon as possible and remain clean at all times. He is asking you to help him accomplish this.
The first line contains two integers $N$ and $M$ $(2 <= N, M <= 2000)$ separated by a space.
The following $N$ lines, each will contain a string with $M$ characters.
If there is no way to reach the destination print $-1$.
Otherwise, the output will consist of two lines. The first line will be an integer $X$ where $X$ is the minimum number of steps that will take Vitor to reach his destination. The second line will be a string with length X where the ith character describe the direction that Vitor should take in the ith step. The string only contains these characters:
## Input
The first line contains two integers $N$ and $M$ $(2 <= N, M <= 2000)$ separated by a space.The following $N$ lines, each will contain a string with $M$ characters.
## Output
If there is no way to reach the destination print $-1$.Otherwise, the output will consist of two lines. The first line will be an integer $X$ where $X$ is the minimum number of steps that will take Vitor to reach his destination. The second line will be a string with length X where the ith character describe the direction that Vitor should take in the ith step. The string only contains these characters: "L" describes a step from (x, y) to (a, y) where a < x "R" describes a step from (x, y) to (a, y) where a > x "D" describes a step from (x, y) to (x, b) where b < y "U" describes a step from (x, y) to (x, b) where b > y Print the smallest lexicographical solution if there is more than one.
[samples]
**Definitions**
Let $ N, M \in \mathbb{Z} $ with $ 2 \leq N, M \leq 2000 $.
Let $ G = (V, E) $ be a grid graph of size $ N \times M $, where each cell $ (i, j) $ for $ 1 \leq i \leq N $, $ 1 \leq j \leq M $ is a vertex.
Let $ c_{i,j} \in \{ \text{'.'}, \text{'#'}, \text{'V'}, \text{'D'} \} $ denote the character in cell $ (i, j) $:
- '.' = clean (walkable),
- '#' = blocked,
- 'V' = Vitor’s starting position,
- 'D' = destination.
Let $ S = (s_x, s_y) $ be the unique cell where $ c_{s_x,s_y} = \text{'V'} $.
Let $ T = (t_x, t_y) $ be the unique cell where $ c_{t_x,t_y} = \text{'D'} $.
Let $ E_{\text{adj}} \subseteq V \times V $ be the set of adjacent edges: $ ((i,j), (i',j')) \in E_{\text{adj}} $ iff $ |i - i'| + |j - j'| = 1 $ and $ c_{i,j} = \text{'.'} $ or $ c_{i,j} \in \{ \text{'V'}, \text{'D'} \} $, and similarly for $ (i',j') $.
Let $ E_{\text{tunnel}} \subseteq V \times V $ be the set of tunnel edges: $ ((x_1,y_1), (x_2,y_2)) \in E_{\text{tunnel}} $ iff $ c_{x_1,y_1} = \text{'.'} $, $ c_{x_2,y_2} = \text{'.'} $, and the two cells are connected by a tunnel (condition incomplete — assume symmetric, bidirectional, and defined by problem context).
Let $ E = E_{\text{adj}} \cup E_{\text{tunnel}} $.
**Constraints**
1. $ S \neq T $, both are in the grid.
2. Only '.' , 'V', 'D' cells are traversable.
3. Tunnels connect pairs of clean ('.') cells (exact condition unspecified — assumed to be given implicitly in input).
4. Movement is allowed only along edges in $ E $.
**Objective**
Find the shortest path (minimum number of steps) from $ S $ to $ T $ in $ G = (V, E) $.
If no path exists, output $-1$.
Otherwise, output:
- First line: the minimum number of steps $ X $.
- Second line: a string of length $ X $, where each character is one of $\{ \text{'U'}, \text{'D'}, \text{'L'}, \text{'R'} \} $, representing the sequence of directions taken (Up, Down, Left, Right) from $ S $ to $ T $.