#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

vector<int> board( 9 );
set< vector<int> > reachedState;

void PrintBoard() {
    for ( int row=0; row<3; ++row ) {
	for ( int col=0; col<3; ++col ) cout << board[row*3+col];
	cout << endl;
    }
}

bool IsReachedState( const vector<int>& b ) {
    return reachedState.find( b ) != reachedState.end();
}

void RegisterState( const vector<int>& b ) {
    reachedState.insert( b );
}

bool IsCompleted( const vector<int>& b ) {
    for ( int i=0; i<8; ++i ) {
	if ( b[i] != i+1 ) return false;
    }
    return b[8] == 0;
}

int main() {

    const int dx[4] = { -1, 0, 1,  0 };
    const int dy[4] = {  0, 1, 0, -1 };
    
    int x, y;
    for ( int i=0; i<3; ++i ) {
	for ( int j=0; j<3; ++j ) {
	    cin >> board[i*3+j];
	    if ( board[i*3+j] == 0 ) {
		y = i;
		x = j;
	    }
	}
    }

    //    PrintBoard();

    queue< pair<vector<int>,int> > stateQue;
    stateQue.push( make_pair(board, 0) );

    while ( !stateQue.empty() ) {

	vector<int> state = stateQue.front().first;
	int step = stateQue.front().second;
	stateQue.pop();

	if ( IsCompleted( state ) ) {
	    cout << step << endl;
	    board = state;
	    //	    PrintBoard();
	    break;
	}

	if ( IsReachedState( state ) ) continue;
	RegisterState( state );

	int x, y;
	for ( int i=0; i<9; ++i ) {
	    if ( state[i] == 0 ) {
		x = i%3;
		y = i/3;
		break;
	    }
	}
	
	for ( int i=0; i<4; ++i ) {

	    int nx = x + dx[i];
	    int ny = y + dy[i];

	    if ( nx < 0 || nx > 2 || ny < 0 || ny > 2 ) continue;

	    vector<int> next = state;
	    swap( next[3*y+x], next[3*ny+nx] );
	    stateQue.push( make_pair( next, step+1 ) );
	    
	}
	
    }
    
    return 0;
}


### Prompt

Generate a Cpp solution to 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 <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

vector<int> board( 9 );
set< vector<int> > reachedState;

void PrintBoard() {
    for ( int row=0; row<3; ++row ) {
	for ( int col=0; col<3; ++col ) cout << board[row*3+col];
	cout << endl;
    }
}

bool IsReachedState( const vector<int>& b ) {
    return reachedState.find( b ) != reachedState.end();
}

void RegisterState( const vector<int>& b ) {
    reachedState.insert( b );
}

bool IsCompleted( const vector<int>& b ) {
    for ( int i=0; i<8; ++i ) {
	if ( b[i] != i+1 ) return false;
    }
    return b[8] == 0;
}

int main() {

    const int dx[4] = { -1, 0, 1,  0 };
    const int dy[4] = {  0, 1, 0, -1 };
    
    int x, y;
    for ( int i=0; i<3; ++i ) {
	for ( int j=0; j<3; ++j ) {
	    cin >> board[i*3+j];
	    if ( board[i*3+j] == 0 ) {
		y = i;
		x = j;
	    }
	}
    }

    //    PrintBoard();

    queue< pair<vector<int>,int> > stateQue;
    stateQue.push( make_pair(board, 0) );

    while ( !stateQue.empty() ) {

	vector<int> state = stateQue.front().first;
	int step = stateQue.front().second;
	stateQue.pop();

	if ( IsCompleted( state ) ) {
	    cout << step << endl;
	    board = state;
	    //	    PrintBoard();
	    break;
	}

	if ( IsReachedState( state ) ) continue;
	RegisterState( state );

	int x, y;
	for ( int i=0; i<9; ++i ) {
	    if ( state[i] == 0 ) {
		x = i%3;
		y = i/3;
		break;
	    }
	}
	
	for ( int i=0; i<4; ++i ) {

	    int nx = x + dx[i];
	    int ny = y + dy[i];

	    if ( nx < 0 || nx > 2 || ny < 0 || ny > 2 ) continue;

	    vector<int> next = state;
	    swap( next[3*y+x], next[3*ny+nx] );
	    stateQue.push( make_pair( next, step+1 ) );
	    
	}
	
    }
    
    return 0;
}


```