Сложная олимпиадная задача-игровое поле размером 3х3, заполненное числами от 1 до 9, обойти все клетки составив максимальное число

[Руслан666]

У пети имеется игровое поле размером 3х3, заполненное числами от 1 до 9. В начале игры он может поставить фишку в любую клетку поля. На каждом шаге игры разрешается перемещать фишку в любую соседнюю по стороне клетку, но не разрешается посещать одну и ту же клетку дважды. Петя внимательно ведет протокол игры, записывая в него цифры в том порядке, в котором фишка посещала клетки. Пете стало интересно, какое максимальное число он может получить в протоколе. Помогите ему ответить на этот вопрос.
Формат входных данных
Входной файл содержит описание поля - 3 строки по 3 целых числа, разделенных пробелами.
Гарантируется, что все девять чсле различны и лежат в диапозоне от 1 до 9.
Формат выходных данных
Выведите одно целое число - максимальное число, которое могло получиться в протоколе при игре на данном поле. Ответ можно выводить не в виде числа а в виде строки или в виде последовательности цифр(не разделяя их пробелами)