Congruent Partition of Chocolate

Time limit30sMemory limit128 MB

Summary

Given a connected polyomino of at most 36 unit squares, decide whether it splits into two connected pieces that are congruent under rotation, reflection, and translation.

Level: Hard9 of 10
Topics: Brute force, DFS, Backtracking, Geometry
Solved: No attempts yet

Problem

The twins Tatsuya and Kazuya love chocolate. They have found a bar of their favorite chocolate in a very strange shape — it looks as though their Mom has already eaten part of it. They plan to cut what is left into two pieces, one for each of them. To be sure the division is fair, they demand that the two pieces are congruent and that each piece is connected.

The chocolate bar is built from unit square blocks. Two blocks are joined when they share an edge, and the whole remaining bar is connected. You may cut the bar only along the edges of the unit squares.

For example, a partially eaten bar with 18 blocks can be cut into two connected pieces of 9 blocks each; rotating one piece by a right angle and turning it over makes it fit exactly onto the other.

Two blocks that touch only at a corner are not considered connected. Because of this, some bars cannot be divided into two congruent connected pieces even though they could be divided into two congruent pieces if connectivity were ignored.

Congruent means that one piece can be made to coincide with the other by any combination of rotation, reflection (turning it over), and translation. Given the shape of a chocolate bar, decide whether it can be partitioned into two congruent and connected pieces.

Input

The input is a sequence of datasets. The end of the input is a line containing two zeros separated by a space. Each dataset has the following format:

w h
r(1, 1) ... r(1, w)
r(2, 1) ... r(2, w)
...
r(h, 1) ... r(h, w)

$w$ and $h$ are the width and the height of the chocolate bar, with $2 \le w \le 10$ and $2 \le h \le 10$ . Each of the next $h$ lines contains $w$ digits separated by single spaces. The digit $r(i, j)$ describes the block at row $i$ , column $j$ :

0: there is no chocolate here (already eaten).
1: there is a chocolate block here.

You may assume that a dataset contains at most 36 blocks (at most 36 digits equal to 1), that every row and every column contains at least one block, that the bar is connected, and that the bar has no holes.

Output

For each dataset, print a single line containing either YES or NO. Print YES if the bar can be partitioned into two congruent and connected pieces, and NO otherwise. The line must contain no other characters.

Examples3

Example 1

Input

2 2
1 1
1 1
3 3
0 1 0
1 1 0
1 1 1
4 6
1 1 1 0
1 1 1 1
1 1 1 0
1 1 1 0
0 1 1 0
1 1 1 0
7 5
0 0 1 0 0 1 1
0 1 1 1 1 1 0
0 1 1 1 1 1 0
1 1 1 1 1 1 0
1 0 0 0 1 1 0
9 7
0 0 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0
1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1
0 0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0
9 7
0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0
7 6
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 0
1 1 1 1 1 1 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
10 10
0 1 1 1 1 1 1 1 1 1
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 0
0 0

Expected output

YES
NO
YES
YES
YES
NO
NO
YES

Example 2
Input
```
2 2
1 1
1 1
0 0
```
Expected output
```
YES
```
Example 3
Input
```
3 2
1 1 1
0 1 0
0 0
```
Expected output
```
NO
```