eolymp
bolt
Try our new interface for solving problems
Məsələlər

Путешествие коня

Путешествие коня

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Коню скучно видеть одни и те же черные и белые клетки каждый раз снова и снова, и он решил совершить путешествие по всему миру. Конь может перемещаться на две клетки в одном направлении и на одну клетку в направлении, перпендикулярном к предыдущему. Конь путешествует по своему миру всё дальше и дальше. Наш конь живет на шахматной доске, которая имеет меньшую площадь, чем обычная 8×8 доска, но все же является прямоугольной. Можете ли вы помочь этой авантюрной затее коня совершить своё путешествие?

Для этого вам необходимо найти такой путь, на котором конь посещает каждую клетку только один раз. Путь коня может начинаться и заканчиваться в любой клетке доски.

Giriş verilənləri

Входные данные начинаются с натурального n в первой строке. Следующие n строк содержат описания каждого из n тестовых случаев. Каждый тест состоит из одной строки, содержащей два натуральных числа p и q таких, что 1p×q26. Это описание задаёт шахматную доску размером p×q, где p описывает различные клетки числами 1, ..., p, а q описывает обозначения клеток буквами соответственно. Это первые q букв латинского алфавита: A, ..., Z .

Çıxış verilənləri

Выходные данные для каждого тестового случая начинается со строки, содержащей "Scenario #i:", где i - это номер тестового случая, начиная с 1. Далее необходимо вывести одну строку, содержащую лексикографически первый путь, следуя по которому конь посещает все клетки шахматной доски. После каждого тестового случая выводите пустую строку. Описание путь выводить в одной строке, последовательно указывая имена посещённых клеток. Имя каждой клетки состоит из заглавной латинской буквы, за которой следует число.

Если такого пути не существует, необходимо вывести в отдельной строке"impossible".

Nümunə

Giriş verilənləri #1
3
1 1
2 3
4 3
Çıxış verilənləri #1
Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4