Гра
Напевно всім знайома дитяча гра «п'ятнашки». У цій задачі ми розглянемо більш просту гру - «восьмушки». Ігрове поле у цій грі являє собою квадрат розміром 3х3 клітинки. Є 8 квадратних фішок, пронумерованих цифрами від 1 до 8. Ці фішки у довільному порядку розставлено у клітинках поля. Одна клітинка залишається вільною. За один хід можна перемістити на вільну клітинку поля довільну з сусідніх фішок, тобто фішку, яка стоїть праворуч або ліворуч, або зверху або знизу від вільної клітинки. Мета гри — переміщуючи фішки по ігровому полю описаним вище способом, розставити всі фішки у вірному порядку:
123
456
780
цифрою 0 позначено вільну клітинку. Вам необхідно для заданого початкового положення фішок визначити мінімальну кількість ходів, за яку можна розставити фішки у вірному порядку.
Вхідні дані
Вхідний файл містить початкову позицію у грі. Позиція задається трьома рядками, у кожному з яких записано три цифри без пропусків. Для задання позиції використовуються цифри від 0 до 8. Кожна цифра зустрічається рівно один раз.
Вихідні дані
Эдиний рядок вихідного файлу повинен містити мінімальну кількість ходів, за яку можна розставити фішки у правильному порядку. Якщо вхідні дані такі, що фішки розставити не можна, необхідно вивести -1 (мінус один). Виведення повинно завершуватись переведенням рядка.