Problem:
 Score : 700 points    Problem Statement There is an H \times W grid ( H vertical, W horizontal), where each square contains a lowercase English letter.
Specifically, the letter in the square at the i -th row and j -th column is equal to the j -th character in the string S_i .  Snuke can apply the following operation to this grid any number of times:   Choose two different rows and swap them. Or, choose two different columns and swap them.   Snuke wants this grid to be symmetric .
That is, for any 1 \leq i \leq H and 1 \leq j \leq W , the letter in the square at the i -th row and j -th column and the letter in the square at the (H + 1 - i) -th row and (W + 1 - j) -th column should be equal.  Determine if Snuke can achieve this objective.      Constraints  1 \leq H \leq 12  1 \leq W \leq 12  |S_i| = W  S_i consists of lowercase English letters.         Input Input is given from Standard Input in the following format:  H  W  S_1  S_2  :  S_H       Output If Snuke can make the grid symmetric, print YES ; if he cannot, print NO .        Sample Input 1 2 3
arc
rac      Sample Output 1 YES  If the second and third columns from the left are swapped, the grid becomes symmetric, as shown in the image below:        Sample Input 2 3 7
atcoder
regular
contest      Sample Output 2 NO       Sample Input 3 12 12
bimonigaloaf
faurwlkbleht
dexwimqxzxbb
lxdgyoifcxid
ydxiliocfdgx
nfoabgilamoi
ibxbdqmzxxwe
pqirylfrcrnf
wtehfkllbura
yfrnpflcrirq
wvcclwgiubrk
lkbrwgwuiccv      Sample Output 3 YES

Solution (Python):
"""

https://atcoder.jp/contests/arc095/tasks/arc095_c

列、行の文字の組み合わせは変わらない
→対応する列・行の組み合わせがなければだめ

→では、各組み合わせが2こずつちゃんとあれば必ず可能か…？
→だとしたら制約小さすぎない？？

ab
ba

abc
aba
cba

→多分十分条件ではないけど少なくとも各組み合わせが2こない場合は絶対×
→かつ、端数の文字が1こ以下でないとだめ
ダメな場合はなんだーーー

分からないけど探索すればよさそう
→ペアになる列・行さえ決まればいい

(11*9*7*5*3*1)**2　→ 10^8ぐらい　最大12**2回探索するので…ア
1ms解法は何…

あらかじめありうるペアだけ列挙しておく？
→あとの入れ替えは探索

→最大になるような場合は全部同じ場合なのですぐ答えが見つかる…と信じたい

1234
2341
3412
4123 →このパターンの場合最悪計算量になってしまう…

1234
2341
4123
3412

1243
2314
4132
3421→ok…？

必要十分条件なのか…？　700点だし…？

反例:
12Z34
23Y41
ZYXYZ
41Y23
34Z12


どうやら現実的な時間で解けるらしい
ちゃんと考えよう
→入れ替えた際に保持されるパラメータを考える…？

答えに対し、対称な列と行を入れ替えても問題ない
& 対称な列のset/行のsetを入れ替えても問題ない
→すなわち列・行の対応以外は全く関係ない

=====答えを見た=====
片側だけペアにするのか…
→確かに片側全探索したらもう片方は簡単に判定できる…(裏返しがあるか判定するだけなので)

具体的な実装は…
まずペアを列挙→再帰で適当にやる
→列を入れ替えたとする

次に横で見てって、各ペアの数字が全て対になってる物があるか調べればいい
→ペア通り数 * H * H * W
"""

def pair(end,lis):
    if len(lis) == 0:
        p.append(end)
        return
    else:
        end.append(lis[0])
        del lis[0]
        for j in range(len(lis)):
            pair( end+[lis[j]] , lis[:j]+lis[j+1:])

from sys import stdin
import sys

H,W = map(int,stdin.readline().split())

S = []
for i in range(H):
    s = stdin.readline()
    S.append(s[:-1])



p = []
if W % 2 == 0:
    pair([],[i for i in range(W)])
else:
    tmp = [i for i in range(W)]
    for i in range(W):
        pair([i,i] , tmp[:i] + tmp[i+1:])



for pl in p:
    able = [True] * H
    flag = 0

    for i in range(H):
        if able[i]:
            for j in range(i+1,H):
                if not able[j]:
                    continue

                tmpf = True
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[j][pl[2*w+1]] or S[j][pl[2*w]] != S[i][pl[2*w+1]]:
                        tmpf = False
                        break
                if tmpf:
                    able[i] = False
                    able[j] = False
                    break
            else:
                if H % 2 == 0 or flag == 1:
                    flag = 2
                    break
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[i][pl[2*w+1]]:
                        flag = 2
                        break
                else:
                    flag = 1
                    able[i] = False
                if flag == 2:
                    break
                
    if flag != 2:
        print ("YES")
        break
else:
    print ("NO")

Solution (Python):
from collections import Counter
n,m = map(int,input().split())
grid = [list(input()) for i in range(n)]
def jc(a,b):
  l = len(a)
  used = [0]*l
  for i in range(l):
    if used[i]:
      continue
    for j in range(i+1,l):
      if used[j]:
        continue
      if a[i] == b[j] and b[i] == a[j]:
        used[i] = 1
        used[j] = 1
        break
  if used.count(0) <= l%2:
    return True
  else:
    return False
def judge(a):
  h = len(a)
  w = len(a[0])
  used = [0]*h
  for i in range(h):
    if used[i]:
      continue
    ci = Counter(a[i])
    for j in range(i+1,h):
      if used[j]:
        continue
      cj = Counter(a[j])
      if ci == cj:
        if jc(a[i],a[j]):
          used[i] = 1
          used[j] = 1
          break
  if used.count(0) <= h%2:
    return True
  else:
    return False
gt = list(zip(*grid))
if judge(grid) & judge(gt):
  print("YES")
else:
  print("NO")

Solution (Python):
def check(field):
    tr = list(map(''.join, zip(*field)))
    paired = set()
    center = -1
    for i, col1 in enumerate(tr):
        if i in paired:
            continue
        for j, col2 in enumerate(tr[i + 1:], start=i + 1):
            if j in paired:
                continue
            if col1 == col2[::-1]:
                paired.add(i)
                paired.add(j)
                break
        else:
            if center == -1 and col1 == col1[::-1]:
                center = i
            else:
                return False
    return True


def arrange_row(field, new_field, i, remain):
    if len(remain) == 0:
        return check(new_field)
    j = remain.pop()
    new_field[i] = field[j]
    for k in list(remain):
        remain.remove(k)
        new_field[h - i - 1] = field[k]
        result = arrange_row(field, new_field, i + 1, remain)
        if result:
            return True
        remain.add(k)
    remain.add(j)
    return False


def solve(h, w, field):
    new_field = [None] * h
    remaining_row = set(range(h))

    if h % 2 == 0:
        return arrange_row(field, new_field, 0, remaining_row)

    for i in list(remaining_row):
        remaining_row.remove(i)
        new_field[h // 2] = field[i]
        result = arrange_row(field, new_field, 0, remaining_row)
        if result:
            return True
        remaining_row.add(i)
    return False


h, w = map(int, input().split())
field = [input() for _ in range(h)]
print('YES' if solve(h, w, field) else 'NO')

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


H, W = list(map(int, sys.stdin.buffer.readline().split()))
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]






def test(groups):
    seen = [False] * 6
    order = [-1] * len(groups)
    for i, g in enumerate(groups):
        if g == -1:
            
            order[W // 2] = i
            continue
        if not seen[g]:
            order[g] = i
            seen[g] = True
        else:
            order[~g] = i

    
    

    rows = []
    for s in S:
        row = ''
        for i in order:
            row += s[i]
        rows.append(row)
    ok = [False] * H
    for i in range(H):
        if ok[i]:
            continue
        rev = rows[i][::-1]
        for j in range(i + 1, H):
            if not ok[j] and rows[j] == rev:
                ok[i] = ok[j] = True
                break
    ng_cnt = ok.count(False)
    if ng_cnt == 0:
        return True
    if ng_cnt == 1:
        i = ok.index(False)
        return rows[i] == rows[i][::-1]
    return False


def solve(groups, depth=0):
    if depth == W // 2:
        return test(groups)

    i = 0
    for _ in range(2 if W % 2 == 1 else 1):
        while groups[i] != -1:
            i += 1

        groups[i] = depth
        for j in range(i + 1, W):
            if groups[j] != -1:
                continue
            groups[j] = depth
            if solve(groups, depth + 1):
                return True
            groups[j] = -1
        groups[i] = -1
        i += 1

    return False


groups = [-1] * W
ok = solve(groups)
if ok:
    print('YES')
else:
    print('NO')

Solution (Python):
import sys
from itertools import permutations
from random import randrange
readline = sys.stdin.readline

mod = 10**9+9
base = 2009   
def rollinhash(S):
    N = len(S)           
    has = 0
    for i in range(N):
        s = S[i]
        has = (has*base + s)%mod
    return has

phr = []
while len(set(phr)) != 26:
    phr = [randrange(1, 10**9) for _ in range(26)]
def shash(S):
    N = len(S)            
    has = 0
    for i in range(N):
        has = has + phr[S[i]]*phr[S[N-1-i]]
    return has

H, W = map(int, readline().split())
G = [list(map(ord, readline().strip())) for _ in range(H)]

ans = 'NO'
fh = H//2
ch = H-fh
lir = list(range(H))
seen = set()
for k in permutations(lir, ch):
    k = list(k)
    sk = set(k)
    for i in range(H):
        if i not in sk:
            k.append(i)
    
    sh = shash(k)
    if sh in seen:
        continue
    seen.add(sh)
    
    
    G2 = []
    for j in k:
        G2.append(G[j])
    G2 = list(map(list, zip(*G2)))
    G2h = [rollinhash(g) for g in G2]
    G2hi = [rollinhash(g[::-1]) for g in G2]
    
    used = [False]*W
    w1 = 0
    match = W//2
    while match and w1 < W:
        if used[w1]:
            w1 += 1
            continue
        sa = G2hi[w1]
        for w2 in range(w1+1, W):
            if used[w2]:
                continue
            if G2h[w2] == sa:
                used[w1] = True
                used[w2] = True
                match -= 1
                break
        w1 += 1
    if sum(used) >= W-1:
        if sum(used) == W-1:
            mid = used.index(False)
            if G2h[mid] == G2hi[mid]:
                ans = 'YES'
        else:
            ans = 'YES'
    if ans == 'YES':
        break
print(ans)

Solution (Python):
import sys
import copy

sys.setrecursionlimit(10 ** 6)

def main():
    def per(s, a=[]):
        if not s:
            return [a]
        if len(s) % 2:
            cs = copy.deepcopy(s)
            res = []
            for u in cs:
                s.remove(u)
                res += per(s, [u] + a)
                s.add(u)
            return res
        u = min(s)
        s.remove(u)
        cs = copy.deepcopy(s)
        res = []
        for uu in cs:
            if uu < u: continue
            s.remove(uu)
            res += per(s, a + [u, uu])
            s.add(uu)
        s.add(u)
        return res

    ord_a = ord("a")
    h, w = map(int, input().split())
    t0 = [[ord(c) - ord_a for c in input()] for _ in range(h)]
    h_set = set(range(h))
    pattern = per(h_set)
    
    
    b = h % 2
    for p in pattern:
        t1 = [[] for _ in range(h)]
        if b:
            t1[h // 2] = t0[p[0]]
        i = 0
        for ii in range(b, h, 2):
            t1[i] = t0[p[ii]]
            t1[h - 1 - i] = t0[p[ii + 1]]
            i += 1
        
        
        fin = [False] * w
        mid = (w % 2 == 1)
        br = False
        for j, c0 in enumerate(zip(*t1)):
            if fin[j]: continue
            fin[j] = True
            c0 = c0[::-1]
            for jj, c1 in enumerate(zip(*t1)):
                if jj <= j: continue
                if fin[jj]: continue
                if c0 == c1:
                    fin[jj] = True
                    break
            else:
                if mid and c0 == c0[::-1]:
                    mid = False
                else:
                    br = True
                    break
        if br: continue
        print("YES")
        exit()
    print("NO")

main()

Solution (Python):


from itertools import groupby
H, W = map(int, input().split())
S_ = ["" for _ in range(W)]
T_ = []
for _ in range(H):
    s = input()
    T_.append(s)
    for i, c in enumerate(s):
        S_[i] += c
T = [sorted(t) for t in T_]
S = [sorted(s) for s in S_]
cnt = 0
for _, g in groupby(sorted(T)):
    if len(list(g))%2:
        cnt += 1
if H%2 < cnt:
    print("NO")
    exit()
cnt = 0
for _, g in groupby(sorted(S)):
    if len(list(g))%2:
        cnt += 1
if W%2 < cnt:
    print("NO")
    exit()
if W%2 or H%2:
    print("YES")
    exit()
T1 = []
T2 = []
for i, (_, t) in enumerate(sorted(zip(T, T_))):
    if i%2:
        T1.append(t)
    else:
        T2.append(t)
T_p = T1 + T2[::-1]
S_pp = ["" for _ in range(W)]
for t in T_p:
    for i, c in enumerate(t):
        S_pp[i] += c
S1 = []
S2 = []
for i, (_, s) in enumerate(sorted(zip(S, S_pp))):
    if i%2:
        S1.append(s)
    else:
        S2.append(s)
S_p = S1 + S2[::-1]
for s1, s2 in zip(S_p, S_p[::-1]):
    for c1, c2 in zip(s1, s2[::-1]):
        if c1!=c2:
            print("NO")
            exit()
print("YES")

Solution (Python):
import sys
input = sys.stdin.readline
import itertools
import numpy as np
from scipy.sparse.csgraph import connected_components

H,W = map(int,input().split())
words = np.array([list(input().rstrip()) for _ in range(H)], dtype='U1')

def gen_pair_pattern_even(rest):
    
    if len(rest) == 0:
        yield []
        return
    if len(rest) == 1:
        x = rest.pop()
        yield [(x,x)]
        return
    li = list(rest)
    x = li[0]
    for y in li[1:]:
        se = rest.copy()
        se.remove(x)
        se.remove(y)
        for p in gen_pair_pattern_even(se):
            yield p + [(x,y)]    

def gen_pair_pattern(N):
    if N & 1:
        for n in range(N):
            se = set(x for x in range(N) if x != n)
            for p in gen_pair_pattern_even(se):
                yield p + [(n,n)]
    else:
        for p in gen_pair_pattern_even(set(range(N))):
            yield p

def test(row_pairs):
    graph = np.ones((W,W), dtype = np.bool)
    for r1,r2 in row_pairs:
        graph &= (words[r1][:,None] == words[r2][None,:])
    graph &= graph.T
    se = set(range(W))
    while se:
        removed = False
        for i,j in itertools.combinations(se,2):
            if graph[i,j]:
                se.remove(i)
                se.remove(j)
                removed = True
                break
        if not removed:
            break
    if len(se) > 1:
        return False
    return True

bl = False
for p in gen_pair_pattern(H):
    if test(p):
        bl = True
        break

answer = 'YES' if bl else 'NO'
print(answer)

Solution (Python):
H,W=map(int,input().split())
G=[list(input()) for i in range(H)]
G_t=[list(x) for x in list(zip(*G))]
def Check(G,H,W):
  Paired_y=[False]*H
  for y1 in range(H):
    if Paired_y[y1]:
      continue
    for y2 in range(H):
      if y1==y2 or Paired_y[y2]:
        continue
      Paired_x=[False]*W
      for x1 in range(W):
        if Paired_x[x1]:
          continue
        for x2 in range(W):
          if x1==x2 or Paired_x[x2]:
            continue
          if G[y1][x1]==G[y2][x2] and G[y1][x2]==G[y2][x1]:
            Paired_x[x1]=True
            Paired_x[x2]=True
            break
      if W%2==1:
        if Paired_x.count(False)==1:
          r=Paired_x.index(False)
          if G[y1][r]==G[y2][r]:
            Paired_y[y1]=True
            Paired_y[y2]=True
            break
      else:
        if Paired_x.count(False)==0:
          Paired_y[y1]=True
          Paired_y[y2]=True
          break
  if H%2==1:
    if Paired_y.count(False)==1:
      return True
    else:
      return False
  else:
    if Paired_y.count(False)==0:
      return True
    else:
      return False
  
if Check(G,H,W) and Check(G_t,W,H):
  print("YES")
else:
  print("NO")

Solution (Python):
input = raw_input
range = xrange

n, m = map(int,input().split())
grid = [input() for i in range(n)]

use = [False]*n
cur = []
def backtrack_even(i, rem, addwhat):
    if rem == 0:
        if addwhat != None: cur.append(addwhat)
        check(cur)
        if addwhat != None: cur.pop()
        return
    if use[i]: return backtrack_even(i+1, rem, addwhat)
    use[i] = True; cur.append(i)
    for j in range(i+1, n):
        if use[j]: continue
        use[j] = True; cur.append(j)
        backtrack_even(i+1, rem-2, addwhat)
        use[j] = False; cur.pop()
    use[i] = False; cur.pop()

def backtrack():
    if n%2 == 0: return backtrack_even(0, n, None)
    for i in range(n):
        use[i] = True
        backtrack_even((0 if i else 1), n-1, i)
        use[i] = False

middle_initial = (m%2 == 0)
from collections import Counter
def check(cur):
    P = cur[::2] + cur[1::2][::-1]
    cols = Counter((''.join(grid[P[i]][j] for i in range(n))) for j in range(m))
    
    middle_filled = middle_initial
    rem = m
    while rem:
        w = next(iter(cols))
        cols[w]-= 1; rem-= 1
        if cols[w] == 0: del cols[w]
        w2 = w[::-1]
        if w2 in cols:
            assert cols[w2]
            cols[w2]-= 1; rem-= 1
            if cols[w2] == 0: del cols[w2]
        elif w == w[::-1] and not middle_filled:
            middle_filled = True
        else: return False
    print("YES"); exit()

backtrack()
print("NO")

Solution (Python):
H, W = map(int, input().split())
S = [input() for i in range(H)]
 
def check(l):
    u = [0]*W
    mid = W % 2
    for i in range(W):
        if u[i]:
            continue
        for j in range(i+1, W):
            for p, q in l:
                sp = S[p]; sq = S[q]
                if sp[i] != sq[j] or sp[j] != sq[i]:
                    break
            else:
                u[j] = 1
                break
        else:
            if mid:
                for p, q in l:
                    sp = S[p]; sq = S[q]
                    if sp[i] != sq[i]:
                        break
                else:
                    mid = 0
                    continue
            break
    else:
        return 1
    return 0
 
def make(c, l, u, p):
    while c in u:
        c += 1
    if c == H:
        if check(l):
            print("YES")
            exit(0)
        return
    if p:
        l.append((c, c))
        make(c+1, l, u, 0)
        l.pop()
    for i in range(c+1, H):
        if i in u:
            continue
        u.add(i)
        l.append((c, i))
        make(c+1, l, u, p)
        l.pop()
        u.remove(i)
 
make(0, [], set(), H%2)
print("NO")

Solution (Python):
H, W = map(int, input().split())
S = [input() for i in range(H)]

def check(l):
    u = [0]*W
    mid = W % 2
    for i in range(W):
        if u[i]:
            continue
        for j in range(i+1, W):
            for p, q in l:
                sp = S[p]; sq = S[q]
                if sp[i] != sq[j] or sp[j] != sq[i]:
                    break
            else:
                u[j] = 1
                break
        else:
            if mid:
                for p, q in l:
                    sp = S[p]; sq = S[q]
                    if sp[i] != sq[i]:
                        break
                else:
                    mid = 0
                    continue
            break
    else:
        return 1
    return 0

def make(c, l, u, p):
    while c in u:
        c += 1
    if c == H:
        if check(l):
            print("YES")
            exit(0)
        return
    if p:
        l.append((c, c))
        make(c+1, l, u, 0)
        l.pop()
    for i in range(c+1, H):
        if i in u:
            continue
        u.add(i)
        l.append((c, i))
        make(c+1, l, u, p)
        l.pop()
        u.remove(i)

make(0, [], set(), H%2)
print("NO")

Solution (Python):
def _3():
    from collections import defaultdict

    def can_pair(s1, s2):
        l = []
        for c1, c2 in zip(s1, s2):
            c = sorted([c1, c2])
            if c in l:
                l.remove(c)
            else:
                l.append(c)

        if len(s1) % 2 == 0:
            return len(l) == 0
        else:
            return len(l) == 1 and l[0][0] == l[0][1]

    def pair_graph(s1, s2):
        N = len(s1)
        G = np.zeros([N, N])
        for i in range(N):
            for j in range(i+1, N):
                if s1[i] == s2[j] and s1[j] == s2[i]:
                    G[i, j] = 1
                    G[j, i] = 1
        return G

    import numpy as np
    H, W = list(map(int, input().split(' ')))
    S = []
    d = defaultdict(list)

    for h in range(H):
        s = input()
        S.append(s)
        d[''.join(sorted(S))].append(h)

    already_paired = np.zeros(H)

    Gs = []

    for i in range(H):
        if already_paired[i]:
            continue

        for j in range(i+1, H):
            if already_paired[j]:
                continue

            if can_pair(S[i], S[j]):
                already_paired[i] = 1
                already_paired[j] = 1
                G = pair_graph(S[i], S[j])
                Gs.append(G)
                break

    if already_paired.sum() < H - 1:
        print('NO')
        exit()

    elif already_paired.sum() == H - 1:
        for i in range(H):
            if already_paired[i] == 0:
                G = pair_graph(S[i], S[i])
                Gs.append(G)
                break

    G = np.array(Gs).sum(axis=0) // len(Gs)

    def is_perfect_matching(G):
        N = len(G)
        if N == 1:
            return True

        for i in range(N):
            for j in range(i+1, N):
                if G[i, j] == 1:
                    l = list(range(N))
                    l.remove(i)
                    l.remove(j)
                    if len(l) == 0:
                        return True
                    if is_perfect_matching(G[l][:, l]):
                        return True
        return False

    if is_perfect_matching(G):
        print('YES')
    else:
        print('NO')

if __name__ == '__main__':
    _3()

Solution (Python):
def _3():
    from collections import defaultdict

    def can_pair(s1, s2):
        l = []
        for c1, c2 in zip(s1, s2):
            c = sorted([c1, c2])
            if c in l:
                l.remove(c)
            else:
                l.append(c)

        if len(s1) % 2 == 0:
            return len(l) == 0
        else:
            if len(l) == 1:
                if l[0][0] == l[0][1]:
                    return True
            return False

    def pair_graph(s1, s2):
        N = len(s1)
        G = np.zeros([N, N])
        for i in range(N):
            for j in range(i+1, N):
                if s1[i] == s2[j] and s1[j] == s2[i]:
                    G[i, j] = 1
                    G[j, i] = 1
        return G

    import numpy as np
    H, W = list(map(int, input().split(' ')))
    S = []
    d = defaultdict(list)

    for h in range(H):
        s = input()
        S.append(s)
        d[''.join(sorted(S))].append(h)

    already_paired = np.zeros(H)

    Gs = []

    for i in range(H):
        if already_paired[i]:
            continue

        for j in range(i+1, H):
            if already_paired[j]:
                continue

            if can_pair(S[i], S[j]):
                already_paired[i] = 1
                already_paired[j] = 1
                G = pair_graph(S[i], S[j])
                Gs.append(G)
                break

    if already_paired.sum() < H - 1:
        print('NO')
        exit()

    elif already_paired.sum() == H - 1:
        for i in range(H):
            if already_paired[i] == 0:
                G = pair_graph(S[i], S[i])
                Gs.append(G)
                break

    G = np.array(Gs).sum(axis=0) // len(Gs)

    def is_perfect_matching(G):
        N = len(G)
        if N == 1:
            return True

        for i in range(N):
            for j in range(i+1, N):
                if G[i, j] == 1:
                    l = list(range(N))
                    l.remove(i)
                    l.remove(j)
                    if len(l) == 0:
                        return True
                    if is_perfect_matching(G[l][:, l]):
                        return True
        return False

    if is_perfect_matching(G):
        print('YES')
    else:
        print('NO')

if __name__ == '__main__':
    _3()

Solution (Python):
H, W = map(int, input().split())
Ss = [input() for _ in range(H)]


def dfs(iR):
    
    if iR < 0:
        return check()

    
    iF = flgs.index(False)
    Rs[iR] = iF - offset
    flgs[iF] = True

    
    ans = False
    for iF2, flg in enumerate(flgs):
        if not flg:
            Rs[H - 1 - iR] = iF2 - offset
            flgs[iF2] = True
            ans = ans or dfs(iR - 1)
            flgs[iF2] = False

    flgs[iF] = False

    return ans



def check():

    Ts = [Ss[R] for R in Rs]
    Ts = list(map(list, zip(*Ts)))

    
    if W % 2: flgCenter = True
    else: flgCenter = False

    
    Used = [False] * W
    for j, T in enumerate(Ts):
        if Used[j]: continue
        for j2, T2 in enumerate(Ts[j + 1:], j + 1):
            
            if not Used[j2] and T[::-1] == T2:
                Used[j2] = True
                break
        else:
            
            if T[::-1] == T and flgCenter == True:
                flgCenter = False
            else:
                
                return False

    return True


if H % 2:
    
    flgs = [False] * (H + 1)
    offset = 1
else:
    flgs = [False] * H
    offset = 0

Rs = [-1] * H
if dfs((H - 1) // 2):
    print('YES')
else:
    print('NO')

Solution (Python):

import numpy as np

H, W = map(int, input().split())
S = list()
for _ in range(H):
    S.append(list(input()))
S_arr = np.array(S)

res = "NO"

def check_col_switch(S_arr, H, W):
    if W % 2 == 1:
        res_bar = -1
    else:
        res_bar = 0
    done_col = np.zeros(W)
    for j in range(W):
        if done_col[j] == 1:
            continue
        rev_j = S_arr[::(-1), j]
        for k in range(W):
            if np.prod(S_arr[:, k] == rev_j) == 1 and j != k and done_col[k] == 0:
                done_col[j] = 1
                done_col[k] = 1
                break
        if done_col[j] == 0:
            if np.prod(S_arr[:, j] == rev_j) == 1:
                done_col[j] = 1
                res_bar += 1
            else:
                res_bar += 10
    if res_bar <= 0:
        return "YES"
    else:
        return "NO"
    
def check_col_switch_fast(S_arr, H, W):
    
    col_raw = np.array(["".join(list(S_arr[:, j])) for j in range(W)])
    col_reverse = np.array(["".join(list(S_arr[::(-1), j])) for j in range(W)])
    
    argsa = np.argsort(col_raw)
    argsb = np.argsort(col_reverse)
    
    res = "YES"
    for j in range(W):
        if col_raw[argsa[j]] != col_reverse[argsb[j]]:
            res = "NO"
            break
    cnt_single = 0
    for j in range(W):
        if argsa[j] == argsb[j]:
            cnt_single += 1
    j = 0
    while j < W-1:
        if col_raw[argsa[j]] != col_raw[argsa[j+1]]:
            cnt_single -= 2
            j += 2
        else:
            j += 1
    if cnt_single >= 2:
        res = "NO"
    
    return res
    
def make_pairs(x_list):
    if len(x_list) <= 2:
        return [[x_list]]
    else:
        res = []
        for j in range(1, len(x_list)):
            x_list_s = [x_list[k] for k in range(1, len(x_list)) if k != j]
            res = res + [[[x_list[0], x_list[j]]] + xl for xl in make_pairs(x_list_s)]
        if len(x_list) % 2 == 1:
            x_list_l = [x_list[k] for k in range(1, len(x_list))]
            res = res + [xl + [[x_list[0]]] for xl in make_pairs(x_list_l)]
        return res
    
def run_row_switch(S_arr, row_matching, H, W):
    S_arr_row = S_arr.copy()
    i = 0
    for mat in row_matching:
        if len(mat) == 2:
            S_arr_row[i, :] = S_arr[mat[0], :]
            S_arr_row[H-1-i, :] = S_arr[mat[1], :]
            i += 1
        else:
            S_arr_row[(H-1)//2, :] = S_arr[mat[0], :]
    return S_arr_row
            
row_match_list = make_pairs([i for i in range(H)])


    


same_row_list = []
for i in range(H):
    j_list = [i]
    for j in range(H):
        if i != j and np.prod(np.sort(S_arr[i, :]) == np.sort(S_arr[j, :])) == 1:
            j_list.append(j)
    same_row_list.append(j_list)
    
def pass_condition(rs):
    res = True
    for pair in rs:
        if len(pair) == 1:
            continue
        if pair[1] not in same_row_list[pair[0]]:
            res = False
            break
    return res

row_match_list_s = [rs for rs in row_match_list if pass_condition(rs)]


for rs in row_match_list_s:
    res = check_col_switch(run_row_switch(S_arr, rs, H, W), H, W)
    if res == "YES":
        break
print(res)