Problem:
 Score : 1100 points    Problem Statement We have a grid with N rows and M columns of squares.
Each integer from 1 to NM is written in this grid once.
The number written in the square at the i -th row from the top and the j -th column from the left is A_{ij} .  You need to rearrange these numbers as follows:   First, for each of the N rows, rearrange the numbers written in it as you like.  Second, for each of the M columns, rearrange the numbers written in it as you like.  Finally, for each of the N rows, rearrange the numbers written in it as you like.   After rearranging the numbers, you want the number written in the square at the i -th row from the top and the j -th column from the left to be M\times (i-1)+j .
Construct one such way to rearrange the numbers. The constraints guarantee that it is always possible to achieve the objective.      Constraints  1 \leq N,M \leq 100  1 \leq A_{ij} \leq NM  A_{ij} are distinct.         Input Input is given from Standard Input in the following format:  N  M  A_{11}  A_{12}  ...  A_{1M}  :  A_{N1}  A_{N2}  ...  A_{NM}       Output Print one way to rearrange the numbers in the following format:  B_{11}  B_{12}  ...  B_{1M}  :  B_{N1}  B_{N2}  ...  B_{NM}  C_{11}  C_{12}  ...  C_{1M}  :  C_{N1}  C_{N2}  ...  C_{NM}   Here B_{ij} is the number written in the square at the i -th row from the top and the j -th column from the left after Step 1 , and C_{ij} is the number written in that square after Step 2 .        Sample Input 1 3 2
2 6
4 3
1 5      Sample Output 1 2 6 
4 3 
5 1 
2 1 
4 3 
5 6       Sample Input 2 3 4
1 4 7 10
2 5 8 11
3 6 9 12      Sample Output 2 1 4 7 10 
5 8 11 2 
9 12 3 6 
1 4 3 2 
5 8 7 6 
9 12 11 10

Solution (Python):

"""

https://atcoder.jp/contests/agc037/tasks/agc037_d

まず分かりやすさのため全部-1してMで割る
2番目の操作後に上から0行目には全部0 , 1行目には全部1…となればおk

すなわち、1番目の操作では各列に1個づつ数字が入るようにする必要がある
→これは貪欲にやればok・・・じゃない

ある列をうまくはめれば必ず次も可能？
→最後の列を考えると、足りない要素と残りの要素のsetは等しいのでokそう
→2部マッチング！

=====解説=====

そもそも何をマッチングさせてた？
→各行の置けるaとa
→   次数は不定 & 不定
→　Hallが成り立つと証明できない…
→　あれ???????正解解法もおかしくないか

"""

from collections import defaultdict
from collections import deque

route = []

def Ford_Fulkerson_Func(s,g,lines,cost):

    global route
    N = len(cost)
    ans = 0
    queue = deque([ [s,float("inf")] ])

    ed = [True] * N
    ed[s] = False

    route = [0] * N
    route[s] = -1

    while queue:

        now,flow = queue.pop()
        for nex in lines[now]:

            if ed[nex]: 
                flow = min(cost[now][nex],flow)
                route[nex] = now
                queue.append([nex,flow])
                ed[nex] = False

                if nex == g:
                    ans += flow
                    break
            
        else:
            continue
        break

    else:
        return False,ans


    t = g
    s = route[t]

    while s != -1:
        cost[s][t] -= flow
        if cost[s][t] == 0:
            lines[s].remove(t)

        if cost[t][s] == 0:
            lines[t].add(s)
        cost[t][s] += flow
        t = s
        s = route[t]

    return True,ans

def Ford_Fulkerson(s,g,lines,cost):

    ans = 0

    while True:
        fl,nans = Ford_Fulkerson_Func(s,g,lines,cost)

        if fl:
            ans += nans
            continue
        else:
            break
    
    return ans


from sys import stdin
import sys
sys.setrecursionlimit(10000)

N,M = map(int,stdin.readline().split())
B = [[None] * M for i in range(N)]

Bs = [[True] * M for i in range(N)]

A = []
for loop in range(N):

    a = list(map(int,stdin.readline().split()))
    A.append(a)

for loop in range(M):

    lines = defaultdict(set)
    cost = [ [0] * (2*N+2) for i in range(2*N+2) ]

    for i in range(N):
        lines[2*N].add(i)
        cost[2*N][i] = 1
    for i in range(N,2*N):
        lines[i].add(2*N+1)
        cost[i][2*N+1] = 1
    for i in range(N):
        for j in range(len(A[i])):
            lines[i].add((A[i][j]-1)//M + N)
            cost[i][(A[i][j]-1)//M + N] = 1

    Ford_Fulkerson(2*N,2*N+1,lines,cost)
    ans = []

    for i in range(N):
        for j in range(len(A[i])):
            if cost[i][(A[i][j]-1)//M + N] == 0:
                ans.append(A[i][j])
                del A[i][j]
                break
    
    for i in range(N):
        B[i][loop] = ans[i]
                

for i in B:
    print (*i)

C = [[None] * M for i in range(N)]
for j in range(M):
    tmp = []
    for i in range(N):
        tmp.append(B[i][j])
    tmp.sort()
    for i in range(N):
        C[i][j] = tmp[i]

for i in C:
    print (*i)

Solution (Python):
import sys
readline = sys.stdin.readline

import collections
class Dinic:
    def __init__(self, vnum):
        self.edge = [[] for i in range(vnum)]
        self.n = vnum
        
        self.inf = float('inf')
    def addedge(self, st, en, c):
        self.edge[st].append([en, c, len(self.edge[en])])
        self.edge[en].append([st, 0, len(self.edge[st])-1])
    def bfs(self, vst):
        dist = [-1]*self.n
        dist[vst] = 0
        Q = collections.deque([vst])
        while Q:
            nv = Q.popleft()
            for vt, c, r in self.edge[nv]:
                if dist[vt] == -1 and c > 0:
                    dist[vt] = dist[nv] + 1
                    Q.append(vt)
        self.dist = dist
    def dfs(self, nv, en, nf):
        nextv = self.nextv
        if nv == en:
            return nf
        dist = self.dist
        ist = nextv[nv]
        for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
            if dist[nv] < dist[vt] and c > 0:
                df = self.dfs(vt, en, min(nf, c))
                if df > 0:
                    self.edge[nv][i][1] -= df
                    self.edge[vt][r][1] += df
                    return df
            nextv[nv] += 1
        return 0
    def getmf(self, st, en):
        mf = 0
        while True:
            self.bfs(st)
            if self.dist[en] == -1:
                break
            self.nextv = [0]*self.n
            while True:
                fl = self.dfs(st, en, self.inf)
                if fl > 0:
                    mf += fl
                else:
                    break
        return mf



N, M = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(N)]


B = [[None]*M for _ in range(N)]

st = 2*N
en = 2*N+1
used = set()
for num in range(M):
    T = Dinic(2*N+2)
    for i in range(N):
        T.addedge(st, i, 1)
        T.addedge(N+i, en, 1)
        for j in range(M):
            aij = A[i][j]
            if aij not in used:
                T.addedge(i, N+(aij-1)//M, 1)
    
    T.getmf(st, en)
    for i in range(N):
        candi = [e for e, cost, _ in T.edge[i+N] if cost == 1][0]
        for j in range(M):
            if A[candi][j] not in used and (A[candi][j]-1)//M == i:
                used.add(A[candi][j])
                B[candi][num] = A[candi][j]
                break
C = list(map(list, zip(*B)))
C = [sorted(c) for c in C]
C = list(map(list, zip(*C)))

for b in B:
    print(*b)

for c in C:
    print(*c)

Solution (Python):
from collections import defaultdict, deque
N, M = map(int, input().split())
A = [[0] * M for _ in range(N)]
B = [[0] * M for _ in range(N)]
C = [[0] * M for _ in range(N)]

G = defaultdict(lambda: defaultdict(int))
F = defaultdict(lambda: defaultdict(int))

rows = [0] * (N * M + 1)

for i in range(N):
    A_list = list(map(int, input().split()))
    A[i] = A_list
    for a in A_list:
        G[i + 1][N + (a + M - 1) // M] += 1
        G[N + (a + M - 1) // M][i + 1] = 0




for t1 in range(M):

    for i in range(1, N + 1):
        G[0][i] = 1
        F[0][i] = 0
        G[N + i][2 * N + 1] = 1
        F[N + i][2 * N + 1] = 0

    for t2 in range(N):
        queue = deque([0])
        searched = [0] * (2 * N + 2)
        searched[0] = 1
        parent = [0] * (2 * N + 2)

        while len(queue) > 0:
            p = queue.pop()
            for q in G[p].keys():
                if (G[p][q] > 0 or F[q][p] > 0) and searched[q] == 0:
                    parent[q] = p
                    searched[q] = 1
                    queue.append(q)
            if searched[2 * N + 1] == 1:
                break
        path = [2 * N + 1]
        while True:
            path.append(parent[path[-1]])
            if path[-1] == 0:
                break

        for i in range(len(path) - 1, 0, -1):
            p, q = path[i], path[i-1]
            if G[p][q] > 0:
                G[p][q] -= 1
                F[p][q] += 1
            elif F[q][p] > 0:
                F[q][p] -= 1
                G[q][p] += 1

    for i in range(1, N + 1):
        ji = 0
        for j in range(N + 1, 2 * N + 1):
            if F[i][j] == 1:
                ji = j
                break

        F[i][ji] -= 1
        for a in A[i - 1]:
            if N + (a + M - 1) // M == ji:
                A[i - 1].remove(a)
                B[i - 1][t1] = a
                break


for j in range(M):
    c_j = list(sorted([B[i][j] for i in range(N)]))
    for i in range(N):
        C[i][j] = c_j[i]
        
if __name__ == "__main__":
    for i in range(N):
        print(*B[i])
    for i in range(N):
        print(*C[i])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

"""
正則二部グラフの辺彩色
"""

import numpy as np

N,M = map(int,input().split())
grid = [[int(x) for x in input().split()] for _ in range(N)]

edge = []
for i,row in enumerate(grid):
    for j,x in enumerate(row):
        edge.append(((x-1)//M,N+i))

graph = [dict() for _ in range(N+N)] 
rest_color = [set(range(M)) for _ in range(N+N)]

for u,v in edge:
    common = rest_color[u] & rest_color[v]
    if common:
        c = common.pop()
        graph[u][c] = v
        graph[v][c] = u
        rest_color[u].remove(c)
        rest_color[v].remove(c)
        continue
    
    c = rest_color[u].pop()
    d = rest_color[v].pop()
    cd = c + d
    V = [u,v]
    next_c = c
    while next_c not in rest_color[v]:
        v = graph[v][next_c]
        V.append(v)
        next_c = cd - next_c
    rest_color[v].remove(next_c)
    rest_color[v].add(cd - next_c)
    for i,(u,v) in enumerate(zip(V,V[1:])):
        if i%2 == 0:
            graph[u][c] = v
            graph[v][c] = u
        else:
            graph[u][d] = v
            graph[v][d] = u

after = [[None] * M for _ in range(N)]

for i,row in enumerate(grid):
    mod_to_x = [[] for _ in range(N)]
    for x in row:
        mod_to_x[(x-1)//M].append(x)
    for color in range(M):
        after[i][color] = mod_to_x[graph[i+N][color]].pop()

B = np.array(after)
C = B.copy()
C.sort(axis = 0)
print('\n'.join(' '.join(row) for row in B.astype(str)))
print('\n'.join(' '.join(row) for row in C.astype(str)))