E - Symmetric Grid

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700

問題文

HW 列のマス目があり,各マスには英小文字が書かれています. 具体的には,上から i 行,左から j 列目のマスに書かれている文字は,文字列 S_ij 文字目に等しいです.

すぬけ君は,このマス目に対して次の操作を好きな回数行うことができます:

  • 2 つの異なる行を選び,入れ替える.または,2 つの異なる列を選び,入れ替える.

すぬけ君は,このマス目が点対称的になるようにしたいです. すなわち,任意の 1 \leq i \leq H, 1 \leq j \leq W に対して,マス目の上から i 行,左から j 列目に書かれている文字と,マス目の上から H + 1 - i 行,左から W + 1 - j 列目に書かれている文字が等しくなるようにしたいです.

すぬけくんがこの目標を達成することが可能かどうか判定してください.

制約

  • 1 \leq H \leq 12
  • 1 \leq W \leq 12
  • |S_i| = W
  • S_i は英小文字のみからなる

入力

入力は以下の形式で標準入力から与えられる。

H W
S_1
S_2
:
S_H

出力

マス目を点対称的にできるなら YES を,できないなら NO を出力せよ.


入力例 1

2 3
arc
rac

出力例 1

YES

下の画像に示すように,左から 2 列目と 3 列目を入れ替えると,マス目が点対称的になります.


入力例 2

3 7
atcoder
regular
contest

出力例 2

NO

入力例 3

12 12
bimonigaloaf
faurwlkbleht
dexwimqxzxbb
lxdgyoifcxid
ydxiliocfdgx
nfoabgilamoi
ibxbdqmzxxwe
pqirylfrcrnf
wtehfkllbura
yfrnpflcrirq
wvcclwgiubrk
lkbrwgwuiccv

出力例 3

YES

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