Amy, 국이 짜다!

Amy는 Farmer John의 며느리이다. Farmer John은 호주 청정우인 Amy를 탐탁지 않게 여기고 있었다. 그러던 어느 날, Amy가 끓인 건초 수프를 맛본 Farmer John은 크게 화를 냈다.

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

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

1. $(r, c)$의 상하좌우에 인접한 네 격자를 $(r+1, c), (r-1, c), (r, c+1), (r, c-1)$라고 한다.
2. 처음에 씽크대가 있는 격자에서 소리가 발생한다. 최초의 소리가 발생하고 1초가 지나면, 소리는 상하좌우로 퍼지고 소멸한다.
3. 씽크대를 제외한 격자 $(r, c)$의 소리는 1초가 지나면 직전에 머무른 격자를 제외한 인접한 세 격자로 퍼진다. 예를 들어 소리가 $(r-1, c)$에서 $(r, c)$로 왔다면 $(r+1, c), (r, c+1), (r, c-1)$로 퍼진다.
4. 격자 $(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이면 소리는 소멸한다.
5. (4)에 의해 이동한 소리는 다른 소리와 부딪히거나 소멸하기 전까지 같은 방향과 속력으로만 계속 이동한다. 인접한 2개 이상의 격자로 퍼지지 않는다.
6. 격자 밖이나 장애물로는 소리가 퍼지지 않고 그곳에서 소멸한다.
7. 소리의 이동은 순간이동으로 취급되어 장애물을 뛰어넘을 수 있다. 도착지를 제외한 경로 위의 빈 격자는 방문하지 않은 것으로 본다. 경로 위에 다른 소리가 있더라도 서로 영향을 받지 않는다.

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

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

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

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

• $1 \le N \le 11$
• 모든 격자 $A_{r,c}$ ($1 \le r,c \le N$)는 씽크대 'S', 빈 격자 '.', 장애물 '@' 중 하나이다.
• 'S'는 반드시 하나 주어진다.