P1368. 拼图

描述 小Barborka刚开始学习拼图。她从一个包含15块的小拼图开始。她的爸爸也想拼这个拼图。为了增加难度，他把所有拼图块都翻转过来，这样他就看不到拼图上的图案了。现在他正在寻找拼图的解决方案。通常应该存在解决方案，但他不确定Barborka是否用另一个类似拼图的某些拼图块替换了原拼图的块。帮助他编写一个程序，该程序读取一组拼图块的描述，并判断是否可以将这些块拼成给定边长的矩形。

输入 输入由多个块组成。除了最后一个块外，每个块都描述一个拼图问题。块的第一行包含整数$n$和$m$，$$0 < n, m <= 6$$，用空格分隔。n和m分别表示拼图的行数和列数。接下来的$$n * m$$行描述各个拼图块。每个拼图块是一个宽$3$厘米、高$4$厘米的矩形，其边的中间可能有凸起或凹槽。对于每个拼图块的每条边，只有一种可能性（见图）：

• 边上没有凸起或凹槽，即边是平的——在拼图时，这样的边只能用于最终图片的边缘，
• 边中间有一个凸起，
• 边中间有一个凹槽。

通常情况下，只有当一个拼图块的边有凸起，另一个拼图块的对应边有凹槽时，两个拼图块才能并排放置。我们用F表示平边，$O$表示有凸起的边，$I$表示有凹槽的边。每个拼图块由四个字母描述，分别表示其上、右、下、左边。为了简化任务，拼图块只能按描述的方式使用，即不能旋转。

每个块之后有一个空行。最后一个块只有一行，包含两个用空格分隔的零，即$$0 0$$。

输出 输出包含对应输入块的行。如果输入块描述的拼图可以正确拼成，则输出$$ YES $$，否则输出$$NO$$。输入的最后一个“空”块在输出中没有对应的行。

输入数据 1

3 5
FOOF
FOOI
FOOI
FOOI
FFOI
IOOF
IOOI
IOOI
IOOI
IFOI
IOFF
IOFI
IOFI
IOFI
IFFI
0 0

输出数据 1

YES

来源 Central Europe 1997