\(O(NM(\sqrt N+\log M))\) 時間でこの問題を解くアルゴリズムを紹介します。 この解説で説明されているアルゴリズムは、37zigen さんのこの記事に書かれているアルゴリズムの（時間計算量のオーダーの面で）下位互換です。

公式解説と同様に、\(O(N ^ {3 / 2}M)\) 時間で \(M\) が \(1\) 小さい問題に帰着することができます。

また、\(M\) が偶数のとき、次のアルゴリズムを用いて \(M\) が半分の問題 \(2\) つに帰着させることができます。

1. 色の塗られていないマスが存在する限り、次を繰り返す。
   1. 色の塗られていないマスのうち、直前に選んだマスと同じ行にあるマスを \(1\) つ選び、赤色で塗る。（直前に選んだマスが存在しないか、直前に選んだマスが含まれる行がすべて塗られていた場合、色の塗られていない好きなマスを選ぶ。）
   2. 色の塗られていないマスのうち、直前に選んだマスと同じ数字が書かれているマスを \(1\) つ選び、青色で塗る。
2. それぞれの行について赤色に塗られたマスのみを取り出したグリッドと、それぞれの行について青色に塗られたマスのみを取り出したグリッドは、それぞれ条件を満たす \(M\) が半分のグリッドになっている。

これで正しく帰着できることは、1-1 で自由にマスを選べる状態ならば、どの行およびどの数字についても赤に塗られているマスの個数と青に塗られているマスの個数が同じになることなどを使って示すことができます。

例えば、サンプル 1 でこのアルゴリズムを行った場合、以下のような操作を行うことができます。

\(A _ {2,1}=2\) および \(A _ {1,1}=1\) を赤く塗っているとき、色が塗られていないマスを自由に選ぶことができることに注意してください。

このアルゴリズムを適切に実装することで、時間計算量を \(O(NM)\) にできます。

今考えている問題の \(M\) が奇数なら公式解説の方法で \(M\) を \(1\) 減らし、偶数なら上のアルゴリズムで列を二等分して再帰することを考えると、これは \(O(N ^ {3 / 2}M\log M)\) 時間でこの問題を解くアルゴリズムになります。

「\(N\) を固定したとき、問題の入力としてありえる \(M _ 1\) と \(M _ 2\) のグリッドを左右に連結させたものも問題の入力としてありえる（ \(=1,2,\ldots,N\) がそれぞれ \(M _ 1+M _ 2\) 回ずつ含まれている）」という事実に注目すると、次のようなアルゴリズムが考えられます。

1. \(M\) を超えない最大の \(2\) べきを \(X\) とし、\(M-X\) 以上の最小の \(2\) べきを \(Y\) とする。上のアルゴリズムで列を二等分したとき、全体のうち左から \(X\) 列目が含まれるほうのみ処理を続ける。
2. 1. が終わったとき、左から \(X\) 列だけを取っても問題の入力としてありえるグリッドになっているため、これを上のアルゴリズムで解く。
3. 2. が終わったとき、右から \(Y\) 列だけを取っても問題の入力としてありえるグリッドになっているため、これを上のアルゴリズムで解く。

それぞれのパートで \(O(N ^ {3 / 2}M)\) 時間、\(O(NM\log M)\) 時間、\(O(NM\log M)\) 時間がかかるので、全体の時間計算量は \(O(NM(\sqrt N+\log M))\) になります。

実装例は以下のようになります。

#include <bit>
#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
#include <queue>

using namespace std;

// N 行 M 列のグリッド A の L 列目から R 列目 (右半開区間) を半分に分ける
// O(NM) 時間
void divide(unsigned N, unsigned M, vector<vector<unsigned>> &A, unsigned L, unsigned R);

// N 行 M 列のグリッド A の L 列目から R 列目 (右半開区間) から 1 列だけ右端に寄せる
// O(NM √N) 時間
void find_one_matching(unsigned N, unsigned M, vector<vector<unsigned>> &A, unsigned L, unsigned R);

int main() {
    unsigned N, M;
    cin >> N >> M;
    vector A(N, vector<unsigned>(M));
    for (auto &&row : A)
        for (auto &&a : row) {
            cin >> a;
            --a;
        }

    // 列数が 2 べきのグリッドを作る
    // while 文はたかだか log(M) + popcount(M) 回繰り返される
    // 1 回ごとに R - L は半分になるので、時間計算量はたかだか O(N^3/2 M)
    unsigned L{}, R{M};
    unsigned x{bit_floor(M)};
    while (L < x && x < R)
        if (1U & (L ^ R))
            find_one_matching(N, M, A, L, R--); // マッチングを作って右端に寄せておく
        else {
            divide(N, M, A, L, R); // 半分にして x を含むほうに移動
            const auto mid{(L + R) / 2};
            (mid < x ? L : R) = mid;
        }

    // 作った 2 べきのグリッドについて解く
    // 時間計算量は O(NM log M)
    unsigned y{bit_ceil(M - x)}, z{M - y};
    for (auto i{x}; i > 1; i /= 2)
        for (auto j{0U}; j < z; j += i)
            divide(N, M, A, j, j + i);

    // 余った部分も列数を 2 べきにかさ増しして解く
    // 時間計算量は O(NM log M)
    for (auto i{y}; i > 1; i /= 2)
        for (auto j{z}; j < M; j += i)
            divide(N, M, A, j, j + i);

    cout << "Yes" << endl;
    for (const auto &row : A) {
        for (const auto a : row)
            cout << a + 1 << " ";
        cout << endl;
    }
    return 0;
}

// 偶数列のとき、半分ずつに分ける
// O(N (R - L)) 時間
constexpr unsigned max_N{bit_ceil(100U)};

void divide(unsigned N, unsigned M, vector<vector<unsigned>> &A, unsigned L, unsigned R) {
    // 列数
    const auto K{R - L};

    // 初期化
    // 各行には K 個の要素が残っている
    auto remaining_element = vector<unsigned>(N, K);

    // すべての行に要素がある
    auto remaining_row = vector<pair<unsigned, unsigned>>(N + 1);
    ranges::copy(views::iota(0U, N + 1) | views::transform([N](auto i) { return make_pair((i + N) % (N + 1), (i + 1) % (N + 1)); }), begin(remaining_row));

    auto row_links = vector(N, vector<pair<unsigned, unsigned>>(M + 1));
    for (auto &&row : row_links) {
        // どの行もすべての要素が残っている
        ranges::copy(views::iota(L, R) | views::transform([M](auto i) { return make_pair(i - 1, i + 1); }), begin(row) + L);
        row[L].first = row[R - 1].second = M;
        row[M] = make_pair(R - 1, L);
    }

    auto num_links = vector(N, vector<pair<pair<unsigned, unsigned>, pair<unsigned, unsigned>>>(M + 1));
    // 要素を見てそれぞれの数字のところに挿入していく
    for (const auto i : views::iota(0U, N))
        num_links[i][M] = make_pair(make_pair(i, M), make_pair(i, M));
    for (const auto j : views::iota(L, R))
        for (const auto i : views::iota(0U, N)) {
            const auto a{A[i][j]};
            const auto&[pi, pj]{num_links[a][M].first};
            num_links[i][j] = make_pair(make_pair(pi, pj), make_pair(a, M));
            num_links[a][M].first = num_links[pi][pj].second = make_pair(i, j);
        }

    // A[row][column] に色を塗る処理
    const auto remove_element{[&](unsigned row, unsigned column) {
        if (!--remaining_element[row]) {
            remaining_row[remaining_row[row].second].first = remaining_row[row].first;
            remaining_row[remaining_row[row].first].second = remaining_row[row].second;
        }
        row_links[row][row_links[row][column].second].first = row_links[row][column].first;
        row_links[row][row_links[row][column].first].second = row_links[row][column].second;
        const auto&[prev, next]{num_links[row][column]};
        const auto&[pi, pj]{prev};
        const auto&[ni, nj]{next};
        num_links[pi][pj].second = next;
        num_links[ni][nj].first = prev;
    }};

    while (remaining_row.back().second != N) { // 残っている行があるなら
        auto now_row{remaining_row.back().second}; // 残っている一番上の行から探索を始める
        while (row_links[now_row][M].second != M) { // 今見ている行に残っている要素があれば
            // 先頭の要素を前半に
            const auto now_column{row_links[now_row][M].second};
            auto next_number{A[now_row][now_column]};
            remove_element(now_row, now_column);

            // 同じ数字の要素を選んで後半に
            const auto&[next_row, next_column]{num_links[next_number][M].first};
            now_row = next_row;
            A[next_row][next_column] |= max_N;
            remove_element(next_row, next_column);
        }
    }

    // 前半と後半に分ける
    for (auto &&row : A)
        ranges::partition(ranges::subrange(begin(row) + L, begin(row) + R), [](auto &&i) { return !(i & max_N); });
    for (auto &&row : A)
        for (auto &&a : ranges::subrange(begin(row) + L, begin(row) + R))
            a &= max_N - 1;
}

// 奇数列のとき、1 つマッチングを作る
// O(N^3/2 (R - L)) 時間
// 参考: https://judge.yosupo.jp/submission/154408
void find_one_matching(unsigned N, unsigned M, vector<vector<unsigned>> &A, unsigned L, unsigned R) {
    // マッチングに使われている要素の情報
    // row_to_column[i] := i 行目に使われている要素がないとき M 、そうでなければ使われている要素の列番号
    // num_to_row[i] := 数字 i が使われていないとき N 、そうでなければ使っている行の番号
    vector<unsigned> row_to_column(N, M), num_to_row(N, N);

    // 探索に使う情報
    // root[i] := i に到達したときに探索を開始した行
    // prev[i] := i の直前に探索した行
    // pcol[i] := prev[i] から i に到達するときに使った列 (A[i][num_to_row[i]] = A[prev[i]][pcol[i]] が成り立つ)
    vector<unsigned> root(N), prev(N), pcol(N);

    // 幅優先探索
    queue<unsigned> que;
    while (true) {
        // 初期化
        ranges::fill(root, N);
        ranges::fill(prev, N);

        // マッチングに使われていない行があれば、キューに入れる
        for (const auto i : views::iota(0U, N))
            if (row_to_column[i] == M)
                que.emplace(root[i] = prev[i] = i);

        bool increase{false}; // 増加道が見つかったか
        while (!empty(que)) {
            auto row{que.front()};
            que.pop();
            if (row_to_column[root[row]] != M) continue; // すでに増加道に使われていたら探索しない

            for (auto column : views::iota(L, R)) {
                auto num{A[row][column]};

                // 増加道が見つかったら遡りながらマッチングを更新
                if (num_to_row[num] == N) {
                    while (true) {
                        num_to_row[num] = row;
                        row_to_column[row] = column;
                        column = pcol[row];
                        if (row == root[row])break;
                        row = prev[row];
                        num = A[row][column];
                    }
                    increase = true;
                    break;
                }

                // まだ探索していない頂点があったらキューに追加
                if (prev[num_to_row[num]] == N) {
                    que.emplace(num_to_row[num]);
                    prev[num_to_row[num]] = row;
                    pcol[num_to_row[num]] = column;
                    root[num_to_row[num]] = root[row];
                }
            }
        }
        if (!increase) break;
    }

    for (const auto i : views::iota(0U, N))
        swap(A[i][R - 1], A[i][row_to_column[i]]);
}