Sliding Puzzle

Time limit

Memory limit

32 MB

Problem

A 3x3 board contains the numbers from 0 to 8, one number in each cell. The number 0 represents the empty cell. The goal state is:


1	2	3
4	5	6
7	8	0

In one move, you may swap the empty cell with one number directly above, below, left, or right of it. A move cannot go outside the board.

Given an initial board, find the minimum number of moves needed to reach the goal state.

Input

The current board is given over three lines. Each line contains three integers separated by spaces. The empty cell is written as 0, and each number from 0 to 8 appears exactly once.

Output

Print the minimum number of moves needed to reach the goal state. If the goal state cannot be reached, print -1.