P17306 [ICPC 2026 Xi'an I] Yesterday Once More (Hard Version)

**这是本题的困难版本。简单版本和困难版本的唯一区别在于你给出的方案的移动次数限制。** Yuki 生活在一个 $n + 1$ 行 $n$ 列的棋盘上。棋盘从上至下依次为第 $1$ 行至第 $n + 1$ 行，从左至右依次为第 $1$ 列至第 $n$ 列。设 $(i, j)$ 表示棋盘上第 $i$ 行第 $j$ 列的格子。 棋盘上共有 $n - 1$ 个格子中有障碍，且这些障碍的分布满足： - 第 $1$ 行和第 $n + 1$ 行中没有障碍。 - 对于所有 $2 \le i \le n$，第 $i$ 行中有 **恰好** 一个障碍。 - 对于所有 $1 \le j \le n$，第 $j$ 列中有 **至多** 一个障碍。 初始时，Yuki 位于 $(1, 1)$；她听说棋盘的第 $n + 1$ 行生活着一群袋鼠，因此她想去棋盘的第 $n + 1$ 行，看看那边的风景。 为了实现目标，Yuki 可以进行若干次移动。每次移动，她需要选定上下左右中的一个方向，并向该方向移动一个格子。特殊地，若该格子位于棋盘外或该格子中有障碍，则此次移动不会被执行。 糟糕的是，Yuki 只知道障碍的分布规则，并不知道障碍的具体分布方式。因此，她希望你帮助她指定每次移动的方向，使得对于任意满足要求的障碍分布方式，Yuki 都 **到达过** 棋盘的第 $n + 1$ 行（她只希望她到达过第 $n + 1$ 行就好，不需要保证在所有移动结束后 Yuki 仍位于第 $n + 1$ 行）。 由于 Yuki 十分着急，你给出的方案的移动次数不能大于 $\boldsymbol{10 \cdot n}$。

共一行，包含一个正整数 $n$ $(2 \le n \le 10^3)$。

第一行，输出一个整数 $k$ $(1 \le k \le 10 \cdot n)$，表示你给出的方案的移动次数。 第二行，输出一个长度为 $k$ 的字符串 $s$，其中 $s_i$ 表示第 $i$ 次移动中 Yuki 的移动方向： - 若 $s_i = \texttt U$，则表示第 $i$ 次移动中 Yuki 的移动方向为向上。 - 若 $s_i = \texttt D$，则表示第 $i$ 次移动中 Yuki 的移动方向为向下。 - 若 $s_i = \texttt L$，则表示第 $i$ 次移动中 Yuki 的移动方向为向左。 - 若 $s_i = \texttt R$，则表示第 $i$ 次移动中 Yuki 的移动方向为向右。

对于第 $1$ 组样例： - 设灰色格子表示有障碍的格子，白色格子表示没有障碍的格子，则下图给出了所有满足要求的障碍分布方式： :::align{center}  ::: - 对于第 $1$ 种障碍分布方式，Yuki 的移动路径为 $(1,1) \to (1,1) \to (1,2) \to (2,2) \to (3,2)$。 - 对于第 $2$ 种障碍分布方式，Yuki 的移动路径为 $(1,1) \to (2,1) \to (2,1) \to (3,1) \to (3,1)$。 - 对于每种满足要求的障碍分布方式，Yuki 都到达过棋盘的第 $n + 1$ 行，因此样例输出正确。 对于第 $2$ 组样例： - 设灰色格子表示有障碍的格子，白色格子表示没有障碍的格子，则下图给出了所有满足要求的障碍分布方式： :::align{center}  ::: - 容易证明，对于其中任意一种障碍分布方式，按照样例输出中给出的移动方式移动，Yuki 都到达过棋盘的第 $n + 1$ 行。