Пятнашки

Обмеження: 2 сек., 256 МіБ

Мабуть усі в дитинтстві бавилися у відому гру — пятнашки. Правила дуже прості: ігрове поле складається з восьми квадратиків, пронумерованих від 1 до 8 і пустого місця. За один хід на пусте місце можна поставити сусідній по горизонталі або вертикалі квадратик. Ціль гри досягкути таку позицію (0 означає порожнє місце):

123
456
780

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

Вхідні дані

Задана початкова ігрова позиція — 3 рядки по 3 числа, не розділених пробілами. Числа від 0 до 8.

Вихідні дані

У єдиному рядку виведіть одне ціле число — мінімальну кількість ходів, за яку можна досягнути цільову позицію, або -1 якщо цільову позицію досягнути не вдасться.

Приклади