사회적 거리 두기

Leila는 수준 높은 병원의 외과의다. 수술실에 가려면 대기실을 지나야 하는데, 그곳에는 코로나바이러스 증상이 있는 환자들이 검사를 받으려고 기다리고 있다. 감염을 피하기 위해 Leila는 환자들과 최대한 멀리 떨어져서 대기실을 통과하려고 한다. 대기실을 지나는 동안 환자로부터 유지할 수 있는 최대 거리를 구하라.

대기실의 지도는 행렬로 주어지며, 환자의 위치와 빈 좌석(Leila가 지나갈 수 없는 곳이다!)의 위치가 표시되어 있다. 행렬에서 두 칸 $(x_1, y_1)$과 $(x_2, y_2)$의 거리는 $\max(|x_1 - x_2|, |y_1 - y_2|)$로 정의한다. 좌석은 코로나의 확산을 막지 못한다. 따라서 두 칸 사이의 거리를 정의할 때 좌석의 위치는 고려하지 않는다. Leila는 각 단계에서 행렬의 한 칸에서 위, 아래, 오른쪽, 왼쪽 네 이웃 칸 중 하나로 이동할 수 있으며, 그곳에 좌석이나 환자가 없어야 한다.

입력의 첫 줄에는 공백으로 구분된 두 정수 $m$ ($1 \le m \le 500$)과 $n$ ($1 \le n \le 500$)이 주어지며, 각각 행의 수와 열의 수다. 그다음 $m$개의 줄에 걸쳐 대기실의 지도가 주어지며, 각 줄은 행렬의 한 행을 나타내고 $n$개의 문자를 포함한다. *는 환자, #는 빈 좌석, .는 Leila가 지나갈 수 있는 빈 공간이다. Leila의 시작 지점은 S, 경로의 도착 지점은 E로 표시된다. Leila는 경로 상에서 행렬로 표현된 대기실 밖으로 나갈 수 없다.

Leila가 경로에서 환자로부터 유지할 수 있는 최대 거리를 출력하라. Leila가 수술실에 도달하는 것이 아예 불가능하면 -1을 출력하라. 그렇지 않고 대기실에 환자가 한 명도 없으면 safe를 출력하라.