题目背景

扶苏正在出发去打 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