眺めてて思ったが、行列とか関係なくね？
それぞれの要素(A1,B1...An,Bn)を小さい順に 1,2,3...N とナンバリングしなおせって問題では？
あとはデータの形式が [A1,B1],[A2,B2],[A3,B3]... になってるから行列のようにも見えるが
冒頭のイメージがあれば [A1,B1] とかはタダのデータ構造でしかない。。

ReorderCards_r0.py

H,W,N = map(int,input().split())
h = []
w = []
for _ in range(N):
    a,b = map(int,input().split())
    h.append(a)
    w.append(b)
 
h_ = sorted(h)#小さい順に並べ替え
w_ = sorted(w)#同上

#以下、辞書で小さい順に格納した key に i+1 と値を埋め込む
dich={}
dicw={}
for i in range(N):
    dich[h_[i]] = i+1
    dicw[w_[i]] = i+1

#冒頭の h, w を一個ずつ辞書に代入して前述の i+1 の順番を取り出した
for a,b in zip(h,w):
    print("{} {}".format(dich[a],dicw[b]))

しかし、見事に WA。
例えば、 [1,2] , [1,3] が与えられたとする。
冒頭の記述だと、

[1,2] を [1,1]
[1,3] を [2,2]

と認識してしまう。
望ましいのは

[1,2] を [1,1]
[1,3] を [1,2]

だ。また、for 文で回す場合は、一個飛ばした場合は、
次の数値が飛ばした値になるから、飛ばした分だけ詰めなければならない。

ReorderCards_r1.py

H,W,N = map(int,input().split())
h = []
w = []
for _ in range(N):
    a,b = map(int,input().split())
    h.append(a)
    w.append(b)
 
h_ = sorted(h)
w_ = sorted(w)
 
dich={}
cnth=0#行の重複をカウント
dicw={}
cntw=0#列の重複をカウント
for i in range(N):
    if h_[i] not in dich:
        dich[h_[i]] = i+1-cnth # 飛ばした分を詰めて辞書に記録
    else:
        cnth += 1              # 飛ばした回数をカウント
 
    if w_[i] not in dicw:
        dicw[w_[i]] = i+1-cntw # 飛ばした分を詰めて辞書に記録
    else:
        cntw += 1              # 飛ばした回数をカウント
 
for a,b in zip(h,w):
    print("{} {}".format(dich[a],dicw[b]))

うん! 説明下手,俺。

解けなかった問題が解けるようになった喜びは半端ない。。