AtCoder Regular Contest 095 - Symmetric Grid

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-----
2 3
arc
rac

-----Sample Output-----
YES

If the second and third columns from the left are swapped, the grid becomes symmetric, as shown in the image below:

Difficulty: VERY_HARD

Starter code:

Solutions:
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')


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()


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')


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')
		return
	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')

def __starting_point():
	_3()
__starting_point()


def check(field):
	tr = list(map(''.join, list(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) = list(map(int, input().split()))
field = [input() for _ in range(h)]
print('YES' if solve(h, w, field) else 'NO')


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)


(H, W) = list(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, 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')


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)


import sys
readline = sys.stdin.readline
read = sys.stdin.read
(h, w) = list(map(int, readline().split()))
s = read().split()
good_move = [[None] * h for _ in range(h)]
for i in range(h):
	for j in range(i, h):
		se = set()
		for p in range(w):
			for q in range(p, w):
				if s[i][p] == s[j][q] and s[i][q] == s[j][p]:
					se.add(p * 16 + q)
		good_move[i][j] = se

def check(q):

	def isok(x, y):
		return all((x * 16 + y in good_move[r[2 * i]][r[2 * i + 1]] for i in range((h + 1) // 2)))

	def dfs2(d, p):
		if d == w:
			return True
		if d == 0 and w & 1:
			for idx in range(w):
				if isok(idx, idx):
					p[idx] = 0
					if dfs2(1, p):
						return True
					p[idx] = -1
			return False
		idx = p.index(-1)
		p[idx] = d
		for k in range(idx + 1, w):
			if p[k] == -1 and isok(idx, k):
				p[k] = d + 1
				if dfs2(d + 2, p):
					return True
				p[k] = -1
		p[idx] = -1
		return False
	r = [0] * h
	for i in range(h):
		r[q[i]] = i
	if h & 1:
		r.append(r[-1])
	p = [-1] * w
	return dfs2(0, p)

def dfs(d):
	nonlocal flag
	if d == h or d == h - 1:
		return check(p)
	if d == 0 and h & 1 and flag:
		flag = 0
		for idx in range(h):
			p[idx] = h - 1
			if dfs(0):
				return True
			p[idx] = -1
		return False
	idx = p.index(-1)
	p[idx] = d
	for k in range(idx + 1, h):
		if p[k] == -1:
			p[k] = d + 1
			if dfs(d + 2):
				return True
			p[k] = -1
	p[idx] = -1
	return False
p = [-1] * h
cnt = 0
flag = 1
if dfs(0):
	print('YES')
else:
	print('NO')


(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')


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)


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')


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
a = [-1] * h
b = [1] * w

def check(x):
	if x == 0:
		return 1
	i = b.index(1)
	if x & 1:
		if all((s[p][i] == s[a[p]][i] for p in range(h))):
			b[i] = 0
			if check(x - 1):
				return 1
			b[i] = 1
	for j in range(i + 1, w):
		if b[j] and all((s[p][i] == s[a[p]][j] for p in range(h))):
			b[i] = b[j] = 0
			if check(x - 2):
				return 1
			b[i] = b[j] = 1
	return 0

def dfs(x):
	if x == 0:
		return check(w)
	i = a.index(-1)
	if x & 1:
		a[i] = i
		if dfs(x - 1):
			return 1
		a[i] = -1
	for j in range(i + 1, h):
		if a[j] == -1:
			(a[i], a[j]) = (j, i)
			if dfs(x - 2):
				return 1
			a[i] = a[j] = -1
	return 0
print('YES' if dfs(h) else 'NO')


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')


(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
			elif 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
	elif 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')