Description

You are given an $R \times C$ map, where . means the cell is walkable and X means the cell is not walkable. Determine whether the map contains any dead ends.

A cell is a dead end if among its four neighboring cells (up, down, left, right), only one cell is walkable. Of course, you cannot move outside the map.

Input Format

The first line contains two positive integers $R, C$.

The next $R$ lines each contain $C$ characters describing the map.

Output Format

If the map contains a dead end, output $1$; otherwise, output $0$.

4 3
XXX
X.X
X.X
XXX

1

5 5
XX.XX
X...X
.....
X...X
XX.XX

1

3 9
...XXX...
.X.....X.
...XXX...

0

Hint

Constraints

For $100\%$ of the testdata, $3 \le R, C \le 10$.

Notes

The score of this problem follows the original COCI settings, with a maximum of $80$ points.

Translated from COCI2011-2012 CONTEST #2 T2 OKRET.

Translated by ChatGPT 5