Знову Лабіринт#4251
Лабіринт такий самий, як у задачі D, і я настійно рекомендую вам спочатку вирішити попередню, оскільки вона легша за цю.
Цього разу ми хочемо, щоб ви розробили команду для нашого бідного робота, щоб він перемістився з місця, де він знаходиться, до місця призначення. Довжина послідовності команд повинна бути найкоротшою. Якщо існує кілька рішень, знайдіть лексикографічно мінімальне. Лексикографічна послідовність — це порядок в одному словнику. Наприклад, "cat" менше ніж "do", а "do" менше ніж "dog".
Перший рядок містить одне ціле число , що вказує на кількість тестових випадків.
Кожен тестовий випадок починається з одного цілого числа (1 \leq N \leq 50), що вказує на розмір лабіринту. Наступні рядків є рядками, довжина яких також , що вказують на лабіринт.
Для кожного випадку виведіть рядок команд, якщо є рішення, інакше виведіть -1.
Приклад 1