L, R, U, D の方向に動く回数をそれぞれ \(L,R,U,D\) とします。

まず、\(1\) 回の移動でマスの場所 \((r,c)\) に対する \(r+c\) の偶奇は変わるので、\(N\) は奇数である必要があります。

また、\((1,1)\) から \((N,N)\) まで移動するので \(R-L=D-U=N-1\) であることを考えると、条件 \(\displaystyle N-1\le K\le \frac{N^2-1}2\) が得られます。さらに、経路の奇数番目のみに注目したマッチングを考えることで \(K\) が偶数という制約も得られます。詳細：\(K\) が偶数であることの証明

以上をまとめると、

• \(N\) が奇数
• \(K\) が偶数
• \(\displaystyle N-1\le K\le \frac{N^2-1}2\)

という条件が必要で、これらが \(1\) つでも満たされない場合答えは No です。

逆に、これらの条件を全て満たす場合答えは Yes です。以下で構成法を説明します。

\(\displaystyle M=\frac{N-1}2\) とします。

まず、整数列 \(\displaystyle T=(T_1,T_2,\ldots,T_M)\) を広義単調減少で \(\displaystyle \frac{N-1}2\geq T_1 \geq T_2\geq \dots \geq T_M\geq 0,\ \sum_{i=1}^M T_i=\frac{K-N+1}2\) を満たすものから任意に \(1\) つ取ります。これは例えば \(\displaystyle T_i=\left\lfloor \frac{\frac K2-i}M\right\rfloor\) とすれば良いです。

そして、以下のように経路を構成できます：

• \(i=1,2,\ldots,M\) の順に以下を行う：
  • R の移動を \(2T_i\) 回行う。
  • D の移動を \(1\) 回行う。
  • L の移動を \(2T_i\) 回行う。
  • D の移動を \(1\) 回行う。
• U, D, R の順に移動できれば移動する、という操作を行う。

このように移動すると条件を全て満たす移動列が構成できます。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

import sys

input = sys.stdin.readline
for _ in range(int(input())):
    n, k = map(int, input().split())
    if n % 2 == 0 or k % 2 == 1 or not (n - 1 <= k <= (n * n - 1) // 2):
        print("No")
        continue
    m = (n - 1) // 2
    s = (k - (n - 1)) // 2
    t = [(s + m - 1 - i) // m for i in range(m)]
    ans = []
    for v in t:
        ans.append("R" * (2 * v))
        ans.append("D")
        ans.append("L" * (2 * v))
        ans.append("D")
    for j in range(1, m + 1):
        d = 2 * (m - sum(v >= j for v in t))
        ans.append("R")
        ans.append("U" * d)
        ans.append("R")
        ans.append("D" * d)
    print("Yes")
    print("".join(ans))