[yLCPC2024] B. 找机厅

扶苏正在出发去打 mai！ 但是商场内部实在太复杂了，她在里面迷路了。已经在地铁站迷路过一次的扶苏看着商场的地图实在是不懂怎么走，你能帮帮她吗？

给定一个 $n$ 行 $m$ 列的 $01$ 矩阵，记矩阵第 $i$ 行第 $j$ 列的格子是 $(i, j)$（$1 \leq i \leq n$，$1 \leq j \leq m$）。 你要从矩阵的左上角出发到达右下角。行走规则如下： - 如果你在格子 $(i, j)$，你下一步只能走到：$(i - 1, j)$、$(i + 1, j)$、$(i, j - 1)$、$(i, j + 1)$ 四个格子的其中之一。 - 任意时刻你不能走出这个矩阵，即你的位置 $(i, j)$ 必须时刻满足 $1 \leq i \leq n$，$1 \leq j \leq m$。 - 如果你想从一个格子走到另一个格子，除了满足上述的要求外，还必须保证：这两个格子对应的数字不同。即：写着 $0$ 的格子只能走到写着 $1$ 的格子，反之亦然。 你每走一步就需要花费一个单位的时间。你需要用最短的时间从 $(1, 1)$ 到达 $(n, m)$。除了给出最短时间外，你还必须给出一种可行的最短用时的行走方法。

**本题单个测试点内有多组测试数据**。第一行是一个正整数 $T$，表示数据组数。对每组数据： 第一行是两个整数 $n, m$（$1 \leq n, m \leq 2 \times 10^3$），表示矩阵的行数和列数。 接下来 $n$ 行，每行一个长度为 $m$ 的仅含字符 `0` `1` 的字符串，表示这个矩阵。 数据保证每组数据内的 $n$ 之和、$m$ 之和均不超过 $2 \times 10^3$。

对每组数据，输出一行或两行： 如果从 $(1, 1)$ 无法到达 $(n, m)$，输出一行一个 $-1$ 表示无解。 否则按如下规则输出： - 第一行输出一个整数 $t$，表示从左上角走到右下角的最短用时。 - 第二行输出一个长度为 $t$ 的仅含字符 `L` `R` `U` `D` 的字符串 $s$，表示你给出的行走方法： + 如果给出的行走方法第 $i$ 次移动是从 $(i, j)$ 走向 $(i - 1, j)$，则 $s_i = \texttt{U}$。 + 如果给出的行走方法第 $i$ 次移动是从 $(i, j)$ 走向 $(i + 1, j)$，则 $s_i = \texttt{D}$。 + 如果给出的行走方法第 $i$ 次移动是从 $(i, j)$ 走向 $(i, j-1)$，则 $s_i = \texttt{L}$。 + 如果给出的行走方法第 $i$ 次移动是从 $(i, j)$ 走向 $(i, j + 1)$，则 $s_i = \texttt{R}$。 你第二行输出的字符串长度必须恰好为第一行给出的最短用时 $t$。如果有多种方案符合要求，你可以输出任意一种。

2
2 2
01
11
2 2
01
10

-1
2
RD