왼쪽 미로

"항상 왼쪽으로 돌라는 지시는, 어떤 미로들의 중앙 안뜰을 찾을 때 흔히 쓰이던 방법을 떠올리게 했다."

— 호르헤 루이스 보르헤스, 《끝없이 두 갈래로 갈라지는 길들이 있는 정원》

한 동료 사서가 방대한 미로 도면 목록을 발굴했고, 우리는 이 미로들을 모두 분류해야 합니다. 각 미로의 도면은 이미 격자(grid)로 디지털화되어 있으며, 각 칸은 벽 블록이거나 바닥입니다.

벽은 연속된 블록들의 나열로, 벽과 벽 사이에 가로 또는 세로 방향의 복도를 만듭니다. 모든 미로에는 정확히 하나의 입구(바깥 벽에 뚫린 하나의 구멍)와 정확히 하나의 중앙 안뜰이 있습니다. 안뜰은 복도와 모양이 다릅니다. 복도는 폭이 한 칸뿐이라 복도의 바닥 칸은 벽 사이에 끼여 있는 반면, 안뜰은 더 넓게 트인 공간입니다. 각 도면에는 미로가 하나만 있으며, 그 바깥 벽 전체가 격자 안에서 이어진다(벽 둘레에 모두 바닥이 있다)고 가정해도 됩니다.

입구에서 출발해 모든 갈림길에서 항상 왼쪽으로 도는 방법으로 걸으면 중앙 안뜰에 도착할 수도, 못 할 수도 있습니다. 구체적으로는 왼손을 벽에 댄 채, 각 걸음에서 왼쪽으로 돌 수 있으면 왼쪽으로, 아니면 직진, 그다음 오른쪽, 마지막으로 뒤돌기 순서로 움직입니다. 이 방법으로 결국 중앙 안뜰에 들어서게 되면 그 미로를 왼쪽 미로라고 부릅니다. 주어진 도면이 왼쪽 미로인지 판정하세요.

첫째 줄에 지도의 줄 수 n이, 둘째 줄에 한 줄당 문자 수 m이 주어집니다. 둘 다 100보다 작습니다.

이어지는 n개의 줄에는 각각 정확히 m개의 문자가 있으며, 각 문자는 #(벽 블록) 또는 .(바닥)입니다.

주어진 미로가 왼쪽 미로이면 YES를, 아니면 NO를 출력합니다.