Задача №657. Путь коня

Дана шахматная доска, состоящая из \(N\)x\(N\) клеток, несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной заданной клетки в другую.

Входные данные

В первой строке задано число \(N\). В следующих \(N\) строках содержится по \(N\) символов. Символом # обозначена вырезанная клетка, точкой - невырезанная клетка, \(@\) - заданные клетки (таких символов два). 2 <= \(N\) <= 50.

Выходные данные

Если путь построить невозможно, вывести "Impossible", в противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом \(@\).

Примеры
Входные данные
2
@.
.@
Выходные данные
Impossible
Входные данные
3
@..
...
..@
Выходные данные
@@.
..@
@.@
Сдать: для сдачи задач необходимо войти в систему