Amy, Soup is Salty!

Amy is the daughter-in-law of Farmer John. Farmer John did not think much of Amy, an Australian clean beef cow. Then one day, Farmer John tasted the hay soup Amy had cooked and flew into a rage.

FJ: [ Amy, the soup is salty! ]
Amy: [ That's just water. ]
FJ: [ The water is salty too! ]
Amy: [ A ship sailing far away cannot go calmly without meeting wind and waves. Wind and waves are always the friends of those who move forward. Joy in life is found in hardship. ]

The moment a water drop hanging from the faucet falls toward the sink, the floor plan of the kitchen where Farmer John and Amy stand is given. The kitchen is a square grid of $N \times N$ cells.

1. Let the cells above, below, right, and left of $(r, c)$ be $(r+1, c), (r-1, c), (r, c+1), (r, c-1)$.
2. At the start, a sound is produced at the cell with the sink. One second later, the initial sound spreads up, down, left, and right, and then disappears.
3. A sound at a cell $(r, c)$ other than the sink spreads one second later to the three adjacent cells except the one it just came from. For example, if the sound came from $(r-1, c)$ to $(r, c)$, it spreads to $(r+1, c), (r, c+1), (r, c-1)$.
4. If sounds from two or more different cells arrive at cell $(r, c)$ at the same time, the sound does not spread to three adjacent cells. Instead, it moves by inertia. Let the previous cells be $(r-dr_{i}, c-dc_{i})$. From one second later, the sound at $(r, c)$ moves with velocity $(\sum_{i} dr_{i}, \sum_{i} dc_{i})$. Note that $|\sum_{i} dr_{i}|$ and $|\sum_{i} dc_{i}|$ can each be natural numbers of 2 or more. However, if $(\sum_{i} dr_{i}, \sum_{i} dc_{i})$ are both 0, the sound disappears.
5. A sound moved by rule (4) keeps moving in the same direction and at the same speed until it collides with another sound or disappears. It does not spread to two or more adjacent cells.
6. Sound does not spread outside the grid or onto obstacles. It disappears there.
7. Sound movement is treated as teleportation, so it can jump over obstacles. Empty cells on the path, other than the destination, are considered unvisited. Other sounds on the path do not affect it.

The eve of the storm. You must determine whether the sound of the water drop falling into the sink can reach every empty cell of the kitchen other than obstacles.

The first line contains the grid size $N$.

The next $N$ lines contain the $N \times N$ floor plan of the kitchen.

Print the minimum time in seconds until the sound has visited every cell other than obstacles at least once. If it is impossible, print -1.

• $1 \le N \le 11$
• Every cell $A_{r,c}$ ($1 \le r,c \le N$) is the sink 'S', an empty cell '.', or an obstacle '@'.
• There is exactly one 'S'.