CF745B.Hongcow Solves A Puzzle

Hongcow likes solving puzzles.

One day, Hongcow finds two identical puzzle pieces, with the instructions "make a rectangle" next to them. The pieces can be described by an n by m grid of characters, where the character 'X' denotes a part of the puzzle and '.' denotes an empty part of the grid. It is guaranteed that the puzzle pieces are one 4-connected piece. See the input format and samples for the exact details on how a jigsaw piece will be specified.

The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions. The puzzle pieces also cannot overlap.

You are given as input the description of one of the pieces. Determine if it is possible to make a rectangle from two identical copies of the given input. The rectangle should be solid, i.e. there should be no empty holes inside it or on its border. Keep in mind that Hongcow is not allowed to flip or rotate pieces and they cannot overlap, i.e. no two 'X' from different pieces can share the same position.

洪 cow 喜欢解谜题。

一天，洪 cow 找到了两个完全相同的拼图块，旁边写着指令：“拼成一个矩形”。每个拼图块可用一个 $n$ 行 $m$ 列的字符网格来描述，其中字符 'X' 表示拼图块的一部分，而 '.' 表示网格中的空白区域。保证该拼图块是一个四连通（4-connected）的整体。关于拼图块的具体输入格式及样例，请参见输入格式说明和样例。

这些拼图块非常重，因此洪 cow 不能旋转或翻转它们。但他可以将它们沿任意方向平移。此外，两个拼图块不能重叠。

你将被给定其中一个拼图块的描述。请判断：能否用两个完全相同的该拼图块（不允许旋转或翻转）拼成一个矩形？该矩形必须是实心的，即其内部及边界上均不能存在任何空洞（即不能有 '.'）。请注意：洪 cow 不允许翻转或旋转拼图块，且两块拼图不能重叠，即来自不同拼图块的两个 'X' 不能占据同一位置。

The first line of input will contain two integers n and m (1 ≤ n, m ≤ 500), the dimensions of the puzzle piece.

The next n lines will describe the jigsaw piece. Each line will have length m and will consist of characters '.' and 'X' only. 'X' corresponds to a part of the puzzle piece, '.' is an empty space.

It is guaranteed there is at least one 'X' character in the input and that the 'X' characters form a 4-connected region.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 500$），表示拼图块的尺寸。

接下来的 $n$ 行将描述该拼图块。每行长度为 $m$，且仅由字符 . 和 X 组成。其中 X 表示拼图块的一部分，. 表示空白区域。

保证输入中至少存在一个 X 字符，且所有 X 字符构成一个四连通区域。

Output "YES" if it is possible for Hongcow to make a rectangle. Output "NO" otherwise.

如果 Hongcow 能够构造出一个矩形，则输出 "YES"；否则输出 "NO"。

For the first sample, one example of a rectangle we can form is as follows

111222
111222

For the second sample, it is impossible to put two of those pieces without rotating or flipping to form a rectangle.

In the third sample, we can shift the first tile by one to the right, and then compose the following rectangle:

.....
..XX.
.....
.....
.....

对于第一个样例，我们可以构造出如下所示的一个矩形：

111222
111222

对于第二个样例，无法在不旋转或翻转的情况下，用两个这样的图形拼成一个矩形。

对于第三个样例，我们可以将第一块方块向右平移一格，然后拼成如下矩形：

.....
..XX.
.....
.....
.....