Game
Surely everyone is familiar children's game "15". In this problem, we consider a simple game - "8". The playing field in this game is a square of 3x3 cells. There are 8 square pieces, numbered with numbers from 1 to 8. These chips are randomly placed in the cells of the field. One cell remains free. In one move, you can move on the free cell field any adjacent chips, ie a chip, standing on the right or left, or top or bottom of the free cells. Goal of the game - moving the pieces on the playing field as described above, to place all the chips in the correct order:
123
456
780
number 0 denotes the empty box. You need to a given initial position of chips to determine the minimum number of moves for which you can arrange the pieces in the correct order.
number 0 denotes the empty box. You need to a given initial position of chips to determine the minimum number of moves for which you can arrange the pieces in the correct order.
Input
The input file contains the starting position in the game. The position is defined by three rows, each of which recorded three digits without spaces. To set the position using numbers from 0 to 8. Each digit occurs exactly once.
Output
The only line in the output file should contain the minimum number of moves for which you can arrange the pieces in the correct order. If the input data such that the chips can arrange, you must withdraw -1 (minus one). The output should end with a newline.
The input file contains the starting position in the game. The position is defined by three rows, each of which recorded three digits without spaces. To set the position using numbers from 0 to 8. Each digit occurs exactly once.