#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <string>
#include <utility>

using namespace std;

#define N (3)
#define N2 (N*N)

struct Puzzle {
    int f[N2];
    int space;
    string path;

    bool operator < ( const Puzzle &p ) const {
	for ( int i = 0; i < N2; i++ ) {
	    if ( f[i] == p.f[i] ) continue;
	    return ( f[i] < p.f[i] );
	}
	return false;		// ????????????????????´???????????\????????????
    }
};

// x, y?????????????????£??????
static const int dx[4] = {-1, 0, 1, 0};
static const int dy[4] = {0, -1, 0, 1};
static const char dir[4] = {'u', 'l', 'd', 'r'};

bool isTarget( Puzzle p ) {
    for ( int i = 0; i < N2; i++ ) {
	if ( p.f[i] != ( i + 1 ) ) return false;
    }
    return true;
}

string bfs( Puzzle s ) {
    queue<Puzzle> Q;
    map<Puzzle, bool> V;
    Puzzle u, v;
    s.path = "";
    Q.push( s );
    V[s] = true;
    
    while ( !Q.empty() ) {
	u = Q.front(); Q.pop();
	if ( isTarget( u ) ) return u.path;
	int sx = u.space / N;
	int sy = u.space % N;
	
	for ( int r = 0; r < 4; r++ ) {
	    int tx = sx + dx[r];
	    int ty = sy + dy[r];

	    if ( tx < 0 || ty < 0 || tx >= N || ty >= N ) continue;
	    v = u;
	    swap( v.f[u.space], v.f[tx * N + ty] );
	    v.space = tx * N + ty;
	    if ( !V[v] ) {
		V[v] = true;
		v.path += dir[r];
		Q.push( v );
	    }
	}
    }

    return "unsolvable";
}

int main()
{
    Puzzle in;
    
    for ( int i = 0; i < N2; i++ ) {
	scanf("%d", &in.f[i]);
	if ( in.f[i] == 0 ) {
	    in.f[i] = N2;
	    in.space = i;
	}
    }
    string ans = bfs( in );

    printf("%d\n", (int)ans.size());

    return 0;
}
### Prompt

In cpp, your task is to solve the following problem:

The goal of the 8 puzzle problem is to complete pieces on $3 \times 3$ cells where one of the cells is empty space.

In this problem, the space is represented by 0 and pieces are represented by integers from 1 to 8 as shown below.


1 3 0
4 2 5
7 8 6


You can move a piece toward the empty space at one step. Your goal is to make the pieces the following configuration in the shortest move (fewest steps).


1 2 3
4 5 6
7 8 0


Write a program which reads an initial state of the puzzle and prints the fewest steps to solve the puzzle.

Constraints

* There is a solution.

Input

The $3 \times 3$ integers denoting the pieces or space are given.

Output

Print the fewest steps in a line.

Example

Input

1 3 0
4 2 5
7 8 6


Output

4

### Response

```cpp
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <string>
#include <utility>

using namespace std;

#define N (3)
#define N2 (N*N)

struct Puzzle {
    int f[N2];
    int space;
    string path;

    bool operator < ( const Puzzle &p ) const {
	for ( int i = 0; i < N2; i++ ) {
	    if ( f[i] == p.f[i] ) continue;
	    return ( f[i] < p.f[i] );
	}
	return false;		// ????????????????????´???????????\????????????
    }
};

// x, y?????????????????£??????
static const int dx[4] = {-1, 0, 1, 0};
static const int dy[4] = {0, -1, 0, 1};
static const char dir[4] = {'u', 'l', 'd', 'r'};

bool isTarget( Puzzle p ) {
    for ( int i = 0; i < N2; i++ ) {
	if ( p.f[i] != ( i + 1 ) ) return false;
    }
    return true;
}

string bfs( Puzzle s ) {
    queue<Puzzle> Q;
    map<Puzzle, bool> V;
    Puzzle u, v;
    s.path = "";
    Q.push( s );
    V[s] = true;
    
    while ( !Q.empty() ) {
	u = Q.front(); Q.pop();
	if ( isTarget( u ) ) return u.path;
	int sx = u.space / N;
	int sy = u.space % N;
	
	for ( int r = 0; r < 4; r++ ) {
	    int tx = sx + dx[r];
	    int ty = sy + dy[r];

	    if ( tx < 0 || ty < 0 || tx >= N || ty >= N ) continue;
	    v = u;
	    swap( v.f[u.space], v.f[tx * N + ty] );
	    v.space = tx * N + ty;
	    if ( !V[v] ) {
		V[v] = true;
		v.path += dir[r];
		Q.push( v );
	    }
	}
    }

    return "unsolvable";
}

int main()
{
    Puzzle in;
    
    for ( int i = 0; i < N2; i++ ) {
	scanf("%d", &in.f[i]);
	if ( in.f[i] == 0 ) {
	    in.f[i] = N2;
	    in.space = i;
	}
    }
    string ans = bfs( in );

    printf("%d\n", (int)ans.size());

    return 0;
}
```