No U-Turns

Sanggeun learned to drive so he could go on drives with his girlfriend. He has become comfortable behind the wheel, but he still cannot make U-turns. Instead of spending more time practicing them, he wants to move to a town where U-turns are unnecessary and prohibited.

The town must not contain any dead ends. If he enters a dead end, he cannot get out without making a U-turn. Given a map of the town, determine whether every road area can be traveled without making a U-turn; equivalently, determine whether the town contains a dead end.

The town map is an R × C grid. Each cell is marked X if it is a building and . if it is a road. From a road cell, he may move to an adjacent road cell in one of the four directions: up, down, left, or right. He cannot move into a building.

If the town has no dead ends, then from any road cell, after moving to any adjacent road cell, he must be able to return to that position without making a U-turn.

A U-turn means immediately moving in the exact opposite direction from the previous move.

The first line contains the town size R and C. (3 ≤ R, C ≤ 10)

The next R lines contain the town map. All road cells are connected to one another, and the town contains at least two road cells.

Print 0 if the town has no dead ends. Otherwise, print 1.