롤러스케이트를 탄 소들

드디어 오랜 부탁 끝에 Farmer John이 마음을 돌려 소 떼 전체를 위해 롤러스케이트를 사 주었습니다. 농장의 많은 부분은 롤러스케이트를 타기에 아주 좋지만, 일부 칸에는 바위가 너무 많아 스케이트로는 지나갈 수 없습니다.

농장은 $R$개의 행과 $C$개의 열로 이루어진 격자로 나타냅니다 ($1 \le R \le 113$, $1 \le C \le 77$). 밥 먹을 시간이 된 Bessie는 칸 $(1, 1)$에 있고, 칸 $(R, C)$에 있는 외양간으로 돌아가려고 합니다. Bessie는 바위가 없는 칸들 사이를 상하좌우로 인접한(대각선은 제외) 칸으로만 이동할 수 있습니다. $(1, 1)$에서 $(R, C)$까지 갈 수 있는 방법이 적어도 하나 존재함이 보장됩니다.

여기서 $(r, c)$는 위에서 $r$번째 행, 왼쪽에서 $c$번째 열에 있는 칸을 뜻합니다.

• 첫째 줄: 공백으로 구분된 두 정수 $R$과 $C$가 주어집니다.
• 다음 $R$개의 줄: 각 줄에는 공백 없이 $C$개의 문자가 주어집니다. 각 문자는 Bessie가 스케이트를 탈 수 있는 칸을 뜻하는 '.' 또는 바위가 너무 많은 칸을 뜻하는 '*' 중 하나입니다. 이 줄들 중 $i$번째 줄의 $j$번째 문자가 칸 $(i, j)$를 나타냅니다. 칸 $(1, 1)$과 $(R, C)$는 항상 '.'입니다.

$(1, 1)$에서 $(R, C)$까지 가는 가장 짧은 경로를 출력합니다. 경로란 $(1, 1)$에서 시작해 $(R, C)$에서 끝나는 칸들의 수열로, 이웃한 두 칸은 변을 공유하도록 상하좌우로 인접해야 하며, 어떤 칸도 바위여서는 안 됩니다. 가장 짧은 경로는 포함된 칸의 수가 가장 적은 경로입니다.

가장 짧은 경로가 여러 개라면, 그중 사전순으로 가장 앞서는 경로를 출력합니다. 두 경로를 칸의 수열로 보고 앞에서부터 비교하며, 각 칸을 $(\text{행}, \text{열})$ 쌍으로 보아 행을 먼저, 그다음 열을 비교합니다.

경로의 각 칸을 한 줄에 하나씩, 공백으로 구분된 두 정수 '행 열' 형태로 출력합니다. 첫 줄은 반드시 '1 1'이어야 하고, 마지막 줄은 반드시 'R C'(즉 $R$과 $C$)여야 합니다.