O Robô Imparável

Um grupo de estudantes estava a desenvolver um robô capaz de se movimentar num labirinto. No entanto, o robô não é perfeito: não consegue mudar de direção nem parar até bater numa parede ou num obstáculo. Assim, quando o robô começa a mover-se, precisa de chegar até à parede mais próxima na direção em que se encontra e só depois pode escolher uma nova direção.

Pede-se que determine qual é o número mínimo de movimentos necessários para o robô ir desde a posição inicial S até à posição final E e que imprima os comandos que os estudantes terão de enviar para o robô conseguir cumprir esse objetivo:

  • L - mover-se para a esquerda

  • U - mover-se para cima

  • R - mover-se para a direita

  • D - mover-se para baixo

Entrada

A primeira linha da entrada contém dois números h e w (2 ≤ h, w ≤ 100), que representam a altura e a largura da grelha.

As h linhas seguintes contêm w carateres que descrevem a grelha:

  • . representa o chão

  • # representa uma parede

  • S indica o ponto de partida

  • E indica o ponto de chegada

Garante-se que a grelha está rodeada por paredes, assegurando que o robô não sai para fora dos limites.

Saída

O programa deve imprimir, na primeira linha, o número mínimo de movimentos para chegar da posição inicial até à final. Na segunda linha, devem aparecer todos os comandos que os estudantes têm de enviar ao robô. Se houver várias soluções, pode ser impressa qualquer uma delas.

Se for impossível levar o robô até ao fim, o programa deve imprimir Impossible.

Exemplos

Input

7 9
#########
#.......#
#.S.....#
#.......#
#.#E....#
#.#.....#
#########
Output

4
RDLU

Sugestão

Pode considerar o ponto de partida como se fosse chão (.) e o ponto de chegada como se fosse uma parede (#).

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue