O Labirinto de Oz

Dorothy está presa em um labirinto mágico e precisa encontrar a saída antes que o tempo acabe. O labirinto é representado por uma grade de N linhas por M colunas, onde cada célula pode conter:

. (ponto): espaço livre

#: parede intransponível

S: posição inicial da Dorothy

E: posição da saída

Dorothy pode se mover para cima, baixo, esquerda ou direita, mas a cada 3 movimentos ela é teletransportada automaticamente de volta para a posição inicial (S). A cada teleporte que acontece, o número de movimentos para o próximo teleporte aumenta em 1, isso significa que após o 3º, 7º, 11º... movimentos, ela reaparece no ponto inicial, mantendo o número de movimentos já feitos.

Seu objetivo é descobrir o menor número de movimentos para que ela complete o percurso.

A primeira linha contém dois inteiros $N$ e $M$ $(1 ≤ N, M ≤ 1000)$, representando as dimensões do labirinto.

As próximas $N$ linhas contêm $M$ caracteres cada, representando o labirinto.

É garantido que existe exatamente um $S$ e um $E$ na grade.

Imprima um único inteiro: o menor número de movimentos necessários para alcançar a saída, ou $-1$ se não for possível.