Background

Fusu is heading out to play mai!

But the mall is way too complicated, and she got lost inside. Having already gotten lost once in the subway station, Fusu stares at the mall map and still cannot figure out where to go. Can you help her?

Problem Description

You are given a $01$ matrix with $n$ rows and $m$ columns. Denote the cell in row $i$ and column $j$ as $(i, j)$ ($1 \leq i \leq n$, $1 \leq j \leq m$).

You need to start from the top-left corner of the matrix and reach the bottom-right corner. The movement rules are as follows:

• If you are at cell $(i, j)$, your next step can only go to one of the following four cells: $(i - 1, j)$, $(i + 1, j)$, $(i, j - 1)$, $(i, j + 1)$.
• At any time, you cannot move out of the matrix, i.e. your position $(i, j)$ must always satisfy $1 \leq i \leq n$, $1 \leq j \leq m$.
• If you want to move from one cell to another, besides meeting the requirements above, you must also ensure that the digits in the two cells are different. That is, a cell containing $0$ can only move to a cell containing $1$, and vice versa.

Each step costs one unit of time. You need to reach $(n, m)$ from $(1, 1)$ in the shortest time. In addition to the shortest time, you must also provide one feasible movement path that achieves this shortest time.

Input Format

This problem contains multiple test cases within a single test point. The first line contains a positive integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n, m$ ($1 \leq n, m \leq 2 \times 10^3$), representing the number of rows and columns of the matrix.
The next $n$ lines each contain a string of length $m$ consisting only of characters 0 and 1, representing the matrix.

It is guaranteed that, within each test case, the sum of all $n$ and the sum of all $m$ do not exceed $2 \times 10^3$.

Output Format

For each test case, output one or two lines:

If it is impossible to reach $(n, m)$ from $(1, 1)$, output one line containing $-1$ to indicate there is no solution.

Otherwise, output according to the following rules:

• The first line outputs an integer $t$, the minimum time needed to go from the top-left corner to the bottom-right corner.
• The second line outputs a string $s$ of length $t$ consisting only of characters L R U D, representing the movement path you provide:
  • If the $i$-th move goes from $(i, j)$ to $(i - 1, j)$, then $s_i = \texttt{U}$.
  • If the $i$-th move goes from $(i, j)$ to $(i + 1, j)$, then $s_i = \texttt{D}$.
  • If the $i$-th move goes from $(i, j)$ to $(i, j-1)$, then $s_i = \texttt{L}$.
  • If the $i$-th move goes from $(i, j)$ to $(i, j + 1)$, then $s_i = \texttt{R}$.

The length of the string on the second line must be exactly the minimum time $t$ given in the first line. If there are multiple valid solutions, you may output any one of them.

2
2 2
01
11
2 2
01
10

-1
2
RD

Hint

Translated by ChatGPT 5