옥수수 미로

지난 가을, Farmer John은 소들을 데리고 옥수수 미로를 구경하러 갔습니다. 그런데 이 미로는 보통 옥수수 미로가 아니었습니다. 중력으로 작동하는 순간이동 미끄럼틀이 여러 개 있어서, 소를 미로의 한 지점에서 다른 지점으로 즉시 이동시켜 줍니다.

각 미끄럼틀은 양방향으로 작동합니다. 소는 미끄럼틀의 시작점에서 끝점으로, 또는 끝점에서 시작점으로 즉시 미끄러져 갈 수 있습니다. 소가 어떤 미끄럼틀의 두 끝점 중 하나가 있는 칸을 밟으면, 반드시 그 미끄럼틀을 이용해야 합니다.

미로의 바깥쪽은 출구 한 곳을 제외하면 모두 옥수수로 둘러싸여 있습니다.

미로는 $N \times M$ 격자로 나타냅니다 ($2 \le N \le 300$, $2 \le M \le 300$). 각 칸에는 다음 중 하나가 들어 있습니다.

• 옥수수 — 지나갈 수 없습니다.
• 잔디 — 자유롭게 지나갈 수 있습니다.
• 미끄럼틀 끝점 — 소를 같은 미끄럼틀의 다른 끝점으로 순간이동시킵니다.
• 출구.

소는 인접한(상·하·좌·우) 두 칸이 모두 옥수수가 아닐 때에만 한 칸에서 이웃한 칸으로 이동할 수 있습니다. 이웃한 칸으로 이동하는 데에는 시간 $1$이 걸리고, 미끄럼틀의 한 끝점에서 다른 끝점으로 미끄러지는 데에는 시간 $0$이 걸립니다.

각 칸은 다음과 같이 표기합니다.

• 옥수수: #
• 잔디: .
• 미끄럼틀 끝점: 같은 대문자(A–Z) 한 쌍. 각 알파벳은 많아야 한 개의 미끄럼틀에만 쓰이므로, 한 미끄럼틀의 두 끝점은 같은 글자를 공유하며 다른 어떤 칸도 그 글자를 쓰지 않습니다.
• 출구: =
• Bessie의 현재 위치: @ (이 칸은 잔디입니다).

Bessie가 길을 잃었습니다. 시작 칸 @이 주어질 때, 출구에 도착하는 데 필요한 최소 시간을 구하세요.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• $2 \ldots N+1$번째 줄: $i+1$번째 줄은 미로의 $i$번째 행을 나타내는 $M$개의 문자(공백 없음)로 이루어져 있습니다.

• 첫째 줄: Bessie가 출구에 도착하는 데 필요한 최소 시간을 나타내는 정수 하나.