答えが存在するための必要十分条件は，

• \(K\geq N\) （証明後述）
• \(N\) が奇数ならば \(K\leq N(N-1)+1\) （\(N\) 頂点グラフのオイラー路の長さの最大値が \(N(N-1)+1\) であるため）

です．

構築方法

まず \(K=N\) を構築します．小さい方から斜めごとに埋めることで達成可能です．あとは斜め \(2\) 列ごとに少しずつ調整できます．

（実装例）

T = int(input())
for _ in range(T):
    N, K = map(int, input().split())
    if K < N or (N % 2 == 1 and K > N * (N - 1) + 1):
        print("No")
        continue

    M = K - N
    ans = [[-1] * N for i in range(N)]
    for i in range(0, N, 2):
        if i + 1 == N:
            for j in range(N):
                ans[(j - 2) % N][j] = i * N + j
            continue
        row1 = [((i + j) % N, j) for j in range(N - 1, -1, -1)]
        row2 = [((i + j) % N, (j + 1) % N) for j in range(N - 1, -1, -1)]
        tmp = i * N
        for i in range(min(M, 2 * N - 2)):
            x, y = row1.pop()
            row1, row2 = row2, row1
            ans[x][y] = tmp
            tmp += 1
        for x, y in row1[::-1] + row2[::-1]:
            ans[x][y] = tmp
            tmp += 1
        M -= min(M, 2 * N - 2)

    print("Yes")
    for row in ans:
        print(*[i + 1 for i in row])

\(K\geq N\) の証明

\(N,A\) を受け取り，小問題の答えを返すジャッジを考えます．

int judge(int N, vector<vector<int>> A) {
  vector<pair<int, int>> order(N * N);
  for (int l = 0; l < N; l++) {
    for (int r = 0; r < N; r++) {
      order[A[l][r] - 1] = {l, r};
    }
  }

  vector<int> dpL(N, 0), dpR(N, 0);
  for (int i = 0; i < N * N; i++) {
    auto [l, r] = order[i];
    int a = dpL[l], b = dpR[r];
    dpL[l] = max(a, b + 1);
    dpR[r] = max(a + 1, b);
  }

  return max(*max_element(dpL.begin(), dpL.end()), *max_element(dpR.begin(), dpR.end()));
}

ここで，10 行目の for 文において，各 \((l,r)\) に対して \(\sum \mathrm{dpL} + \sum \mathrm{dpR}\) は常に \(2\) 以上増加していることが分かります．したがって，最終的な \(\sum \mathrm{dpL} + \sum \mathrm{dpR}\) は \(2N^2\) 以上になるので，\(\max(\max(\mathrm{dpL}),\max(\mathrm{dpR}))\geq N\) です．