유턴은 싫어

상근이는 여자친구와 드라이브를 하려고 운전을 배웠다. 운전은 익숙해졌지만, 유턴만은 여전히 할 수 없다. 그래서 유턴 연습에 시간을 더 쓰는 대신, 유턴할 필요가 없고 유턴이 금지된 마을로 이사하려고 한다.

이 마을에는 막다른 길이 있으면 안 된다. 막다른 길에 들어가면 유턴을 하지 않고는 빠져나올 수 없기 때문이다. 마을 지도가 주어졌을 때, 유턴 없이 모든 길을 돌아다닐 수 있는지, 즉 막다른 길이 있는지 판별하라.

마을 지도는 R × C개의 칸으로 이루어진 격자이다. 각 칸은 건물이면 X, 길이면 .로 표시된다. 길 위에서는 상하좌우 네 방향으로 인접한 길로 이동할 수 있으며, 건물로는 이동할 수 없다.

마을에 막다른 길이 없다면, 어떤 길에서 시작해 어느 인접한 길로 이동하더라도 유턴 없이 다시 그 위치로 돌아올 수 있어야 한다.

유턴은 방금 이동한 방향의 정반대 방향으로 바로 이동하는 것이다.

첫째 줄에 마을의 크기 R과 C가 주어진다. (3 ≤ R, C ≤ 10)

다음 R개 줄에는 마을의 지도가 주어진다. 모든 길은 서로 연결되어 있으며, 마을에는 길이 적어도 두 칸 있다.

마을에 막다른 길이 없다면 0을, 그렇지 않다면 1을 출력한다.