Grid City

Time limit1sMemory limit512 MB

Summary

Given an R x C grid of street tiles, find the fewest 90-degree rotations so every street connects two junctions, or -1 if impossible.

Level: Medium7 of 10
Topics: Graph, Matrix, Implementation
Solved: No attempts yet

Problem

Indonesia is moving its capital from Jakarta to another city in Kalimantan. The national city planners have proposed a new city plan. The new city will be built on a rectangular piece of land, and the plan divides the land into a grid of $R \times C$ cells with $R$ rows and $C$ columns. The planners believe this grid design can represent a "modern" image of Indonesia.

Each cell has exactly one junction at its center. At most 4 streets connect to that junction. Each street runs horizontally or vertically. A cell can have only 14 possible layouts:

The junction connects to exactly zero or four streets (2 possible layouts).
The junction connects to exactly two streets forming an L shape (4 possible layouts).
The junction connects to exactly one street (4 possible layouts).
The junction connects to exactly three streets (4 possible layouts).

The planners found that some streets end without reaching any junction. Such a street serves no purpose because it does not connect two junctions. In the example below with $R = 3$ and $C = 4$ , the triangles mark streets whose end is not on a junction.

To fix this, you can rotate one or more cells clockwise (CW) or counter-clockwise (CCW) by 90 degrees. A 180-degree rotation takes two rotations, either (CW, CW) or (CCW, CCW). The right side of the example shows one arrangement that makes every street connect two different junctions, using a total of 7 rotations.

Find the minimum number of rotations needed so that every street connects two different junctions.

Input

The first line contains two integers $R$ and $C$ ( $1 \le R, C \le 30$ ), the number of rows and columns. Each of the next $R$ lines contains $C$ strings, one per cell. Each string is a 4-bit string in the format NESW, where N, E, S, and W are each 0 or 1. A 1 means a street goes in that direction from the junction, and a 0 means no street does. No cell has the layout 1010 or 0101.

Output

Print one integer on a line: the minimum number of rotations needed so that every street connects two different junctions, or -1 if this is impossible.

Examples2

Example 1

Input

3 4
1001 0011 0100 0001
1100 1111 1110 1001
0000 1000 0010 0010

Expected output

Example 2
Input
```
1 3
0100 0011 0100
```
Expected output
```
-1
```