Maze Again#4251
The maze is the same as problem D, and I strongly recommend you solve the previous one first because it's easier than this.
This time, we want you to design the command for our poor robot to move from where it is to its destination. The command sequence's length should be the shortest. If several solutions exist, find the lexicographically minimum one. Lexicographical sequence is the order in one dictionary. For example, "cat" is less than "do", and "do" is less than "dog".
The first line contains a single integer , indicating the number of test cases.
Each test case begins with one integer (1 \leq N \leq 50), indicating the size of the maze. The followed lines are strings whose length is also , indicating the maze.
For each case, output a command string if there is a solution, otherwise output -1.
Пример 1