SPOJ Brasil

Num futuro não muito distante as pessoas buscarão jogos cada vez mais perigosos para se divertir. Depois de ultra-leve e bungee-jump as pessoas precisarão de jogos em que suas atividades mentais sejam também colocadas a prova. É o caso deste jogo, chamado "cube", inventado na Nova Zelândia. Em alguns lugares o jogo também é conhecido pelo seu nome em japonês: sokoban.

Considere um labirinto bi-dimensional composto por células quadradas, onde cada uma delas ou está livre ou está sendo ocupada por uma pedra. A cada passo, você pode sair de uma célula e mover-se para outra célula vizinha (i.e., cima, baixo, direita e esquerda) livre. Você está ocupando uma das células livres desse labirinto.

Uma célula do labirinto contém uma pilha de caixas. A pilha pode ser movida de uma célula i para uma célula k (por exemplo, k = i+1), vizinha de i, na direção ik se você estiver numa célula j (no caso, j = i-1), vizinha de i , e a direção ik é igual à direção ji. Uma caixa não pode ser movida de qualquer outra maneira (ou seja, você não pode puxá-la para trás). Logo, se ela for parar em algum canto do labirinto, você não será capaz de movê-la novamente. Por fim, note que em cada empurrão você dá um passo, e que o contrário não é necessariamente verdade.

Uma das células vazias é marcada como a célula final. Sua tarefa é trazer a caixa para essa célula final através de uma seqüência de passos e empurrões na caixa. Como a caixa é pesada, você quer realizar o menor número possível de empurrões na caixa.

Observe que no jogo de vida real há a possibilidade de você se prender ou mesmo ser esmagado pela caixa, tornando tudo muito mais divertido.

Entrada

O arquivo de entrada é composto por várias instâncias. Cada instância começa com uma linha contendo dois inteiro r e c (ambos menores ou iguais a 20) representando o número de linhas e colunas do labirinto.

Em seguida, são fornecidas r linhas, cada uma contendo c caracteres. Cada caractere descreve uma célula do labirinto. Uma célula ocupada por uma pedra é indicada por # e uma célula vazia é representada por um "." (sem as aspas). Sua posição inicial é indicada por S, a posição inicial da caixa é indicada por B e a posição final da caixa é indicada por T.

A entrada termina quando r = c = 0.

Saída

Para cada labirinto, inicialmente imprima o número da instância, conforme mostra o exemplo de saída abaixo. Se for impossível levar a caixa até sua posição final, imprima "Impossivel".

Caso contrário, você deve imprimir dois inteiros x e y, onde x indica o número de movimentos (passos + empurrões) e y o número de empurrões de uma seqüência que faz com que você leve a caixa até a posição final. O número de empurrões dever ser minimizado. Caso exista mais de uma seqüência possível que utiliza um número mínimo de empurrões, o número total de movimentos deve ser minimizado. Imprima uma linha em branco após cada instância.

Exemplo

Entrada:
1 7
SB....T
1 7
SB..#.T
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
0 0 

Saída:
Instancia 1
5 5

Instancia 2
Impossivel

Instancia 3
28 6