Amy, Soup is Salty!

문제

Amy는 Farmer John의 며느리이다. Farmer John은 호주 청정우인 Amy를 탐탁치 않게 생각하고 있었다. 그러던 어느 날, Amy가 끓인 건초 수프를 맛 본 Farmer John은 극대노 했다.

FJ: [ Amy야, 국이 짜다! ]
Amy: [ 그건 물인데요. ]
FJ: [ 물도 짜다! ]
Amy: [ 먼 곳을 항해하는 배가 풍파를 만나지 않고 조용히만 갈 수는 없다. 풍파는 언제나 전진하는 자의 벗이다. 차라리 고난 속에 인생의 기쁨이 있다. ]

수도꼭지에 맺힌 물방울이 씽크대를 향해 떨어지는 그 순간, Farmer John과 Amy가 위치한 주방의 평면도가 주어진다. 주방은 $N \times N$ 크기의 정사각형 격자로 표현된다.

$(r, c)$ 의 상하좌우를 인접한 네 격자인 $(r+1, c), (r-1, c), (r, c+1), (r, c-1)$ 라고 하자.
최초에, 씽크대가 있는 격자에서 소리가 발생한다. 최초의 소리가 발생한지 1초가 지나면, 최초의 소리는 상하좌우로 퍼지고 소멸한다.
씽크대를 제외한 격자 $(r, c)$ 의 소리는 1초가 지나면 직전에 머무른 격자를 제외한, 인접한 세 격자로 퍼져 나간다. 예를 들어 소리가 $(r-1, c)$ 에서 $(r, c)$ 로 왔다면, $(r+1, c), (r, c+1), (r, c-1)$ 로 소리가 퍼져 나간다.
격자 $(r, c)$ 에, 동시에, 서로 다른 2개 이상의 격자로부터 소리가 도달하면, 소리는 인접한 세 격자로 퍼지지 않고 관성에 의해 움직인다. 직전 격자들의 위치를 각각 $(r-dr\_{i}, c-dc\_{i})$ 라고 하자. 1초 뒤부터 $(r, c)$ 의 소리는 $(\sum\_{i} dr\_{i}, \sum\_{i} dc\_{i})$ 의 속도로 이동한다. $|\sum\_{i} dr\_{i}|, |\sum\_{i} dc\_{i}|$ 가 각각 2 이상의 자연수일 수 있음에 유의하라. 단, $(\sum\_{i} dr\_{i}, \sum\_{i} dc\_{i})$ 가 모두 0이면 소리는 소멸한다.
(4)에 의해 이동한 소리는 다른 소리와 부딪히거나 소멸하기 전까지 계속 같은 방향과 속력으로만 이동한다. 인접한 2개 이상의 격자로 퍼지지 않는다.
격자 밖 또는 장애물로는 소리가 퍼져 나가지 않고 소멸한다.
소리의 이동은 순간이동으로 취급되어 장애물을 뛰어 넘을 수 있고, 도착지를 제외한 경로 내의 빈 격자는 방문하지 않은 것으로 간주한다. 경로 내에 다른 소리들이 있더라도 서로 영향 받지 않는다.

폭 풍 전 야. 여러분은 물방울이 씽크대에 떨어지는 소리가 장애물을 제외한 주방의 모든 빈 격자에 도달할 수 있는지 판정해야 한다.

입력

첫 번째 줄에 격자의 크기 $N$ 이 주어진다.

두 번째 줄부터 $N$ 개의 줄에 걸쳐 $N \times N$ 크기의 주방의 평면도가 주어진다.

출력

소리가 장애물을 제외한 모든 격자를 한 번 이상 방문하는 데 필요한 최소 시간(초)을 출력한다. 불가능한 경우 -1을 출력한다.

제한

$1 \le N \le 11$
모든 격자 $A\_{r,c}$ ( $1 \le r,c \le N$ )는 씽크대 'S' 또는 빈 격자 '.' 또는 장애물 '@'로 구성되어 있다.
'S'는 반드시 하나 주어진다.