Symmetric Grid

AtCoder

IDarc095_c

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

2 3
arc
rac

Output #1

YES

If the second and third columns from the left are swapped, the grid becomes symmetric, as shown in the image below:
![image](https://img.atcoder.jp/arc095/2b61caf45e7c5c7311e3944f3418b0bb.png)

Input #2

3 7
atcoder
regular
contest

Output #2

NO

Input #3

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

Output #3

YES

API Response (JSON)

{
  "problem": {
    "name": "Symmetric Grid",
    "description": {
      "content": "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 equ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc095_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 equ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments