Finding Snakes

An n x m grid is filled with 0s and 1s. Cells containing 1 may be connected through their four cardinal neighbors to form a shape.

A snake is one connected group of 1-cells. In that group, every cell except the two ends must be adjacent, through the four cardinal directions, to exactly two cells from the same group. An end cell is where the snake starts or finishes, and a group with only one cell is treated as a snake of length 1.

A snake is not maximal if it can be made longer from any end. More precisely, if a 0-cell adjacent to an end can be changed to 1 and that new cell touches only that end, then the snake can simply be extended by one cell and is not maximal. A snake is maximal when no such extension is possible from any end.

Given the grid, count the maximal snakes.

The first line contains two integers n and m (1 <= n, m <= 200).

Each of the next n lines contains the grid information as a string of length m consisting only of 0 and 1.

Print the number of maximal snakes.