Dorm Cleaning Cycle Cover

In a new dormitory building, the rooms are arranged in an N × M grid. Every room has four doors (one on each wall) that lead to its adjacent neighbor in the north, south, east and west directions. Some rooms are used for storage and do not need to be cleaned. Only the remaining cleaning‐required rooms (denoted by 1) must be visited.

The duty student, Xiao A, wishes to design several cleaning routes. The requirements for these routes are as follows:

1. Each cleaning‐required room is visited exactly once – that is, the cleaning route enters and leaves every such room exactly one time.
2. In every room the door used to enter must be different from the door used to exit.
3. Each route must form a closed cycle (i.e. a loop) and must contain more than 2 rooms.
4. The routes are disjoint and together cover all cleaning‐required rooms.

For example, the figures below (with gray cells representing storage rooms) show valid cleaning schemes.

Note that for some layouts there is no possible way to design routes meeting the above criteria. Your task is to determine whether a valid cleaning plan exists for a given room layout.

Mathematical formulation:
Let the grid be represented by an N × M matrix. Define a graph where each cleaning-required room is a vertex. An edge is drawn between two vertices if the corresponding rooms are adjacent (i.e. share a door). A valid cleaning plan corresponds to a cycle cover of this graph such that every vertex is incident with exactly two edges and no cycle has length 2. In a bipartite grid (with natural chessboard colouring), note that every cycle of even length has an equal number of vertices from each partition. Thus a necessary condition is that the number of cleaning-required rooms in the two partitions must be equal. In our solution we reduce the problem of finding such a cycle cover to finding two edge-disjoint perfect matchings in the bipartite graph. We build a flow network as follows:

• Create a source node that connects to each vertex in the left (black) partition with capacity 2.
• For each edge from a left vertex to a right (white) vertex (adjacent cleaning rooms), assign capacity 1.
• Connect each right vertex to the sink with capacity 2.

If the maximum flow in this network equals 2|L| (where |L| is the number of vertices in the left partition), then two disjoint perfect matchings exist and a valid cleaning plan is possible. Otherwise, it is not possible.

inputFormat

The first line of input contains two integers N and M (1 ≤ N, M ≤ 1000) representing the number of rows and columns respectively. The following N lines each contain a string of M characters. Each character is either '1' or '0', where '1' represents a cleaning‐required room and '0' represents a storage room that does not need cleaning.

It is guaranteed that N and M are positive integers.

outputFormat

Output a single line containing either Yes or No. Output Yes if there exists a valid set of cleaning routes satisfying the conditions, and No otherwise.

sample

3 3
111
111
111

No