Let \(L,R,U\) and \(D\) be the number of moves in L, R, U, and D, respectively.

First, any move flips the parity of \(r+c\) for the position of cell \((r,c)\), so \(N\) must be odd.

Also, since we are traveling from \((1,1)\) to \((N,N)\), we obtain a constraint \(\displaystyle N-1\le K\le \frac{N^2-1}2\). Moreover, considering the matching with the odd-indexed entries in the path, we also mandate that \(K\) is even. Details: Proof that \(K\) is even (in Japanese; the translation will be provided later.)

To wrap up, the following conditions are necessary:

• \(N\) is odd.
• \(K\) is even.
• \(\displaystyle N-1\le K\le \frac{N^2-1}2\).

If any of them is violated, the answer is No.

Conversely, the answer is Yes if they are all satisfied; we will prove it by construction.

Let \(\displaystyle M=\frac{N-1}2\).

First, take any integers monotonically non-increasing sequence \(\displaystyle T=(T_1,T_2,\ldots,T_M)\) such that \(\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\). For example, we can let \(\displaystyle T_i=\left\lfloor \frac{\frac K2-i}M\right\rfloor\).

Then, the path can be constructed as follows:

• Do the following for \(i=1,2,\ldots,M\):
  • Move in R direction \(2T_i\) times.
  • Move in D direction \(1\) time.
  • Move in L direction \(2T_i\) times.
  • Move in D direction \(1\) time.
• Move in U, D, and R directions, in this order, if it is possible to do so.

This way indeed constructs a sequence of moves that satisfies all the conditions.

The problem can be solved by properly implementing this algorithm.

Sample code (Python 3)

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))