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

constexpr int NX = 3, NY = 3;
constexpr int SIZE = NX*NY;

using namespace std;

typedef pair< int, vector<int> > PuzzleState;

set< vector<int> > visited;

bool IsSolved( const vector<int>& s ) {
    int cnt = s[SIZE-1] == 0 ? 1 : 0;
    for ( int i=0; i<SIZE; ++i ) {
	if ( s[i] == i+1 ) ++cnt;
    }
    return cnt == SIZE;
}

bool IsVisited( const vector<int>& s ) {
    return visited.find( s ) != visited.end();
}

int Solve( const vector<int>& init_s ) {

    const int dx[4] = { -1,  0, 1, 0 };
    const int dy[4] = {  0, -1, 0, 1 };

    queue< PuzzleState > state;
    state.push( make_pair(0, init_s) );
    visited.insert( init_s );

    while ( !state.empty() ) {

	PuzzleState curr = state.front();

	if ( IsSolved( curr.second ) ) return curr.first;
	state.pop();
	
	int x, y;
	for ( int i=0; i<SIZE; ++i ) {
	    if ( curr.second[i] == 0 ) {
		x = i%NX;
		y = i/NY;
		break;
	    }
	}

	for ( int i=0; i<4; ++i ) {
	    int nx = x + dx[i];
	    int ny = y + dy[i];
	    if ( nx >= 0 && nx < NX && ny >= 0 && ny < NY ) {

		swap( curr.second[NX*y+x], curr.second[NX*ny+nx] );
		curr.first += 1;
		
		if ( !IsVisited( curr.second ) ) {
		    state.push( curr );
		    visited.insert( curr.second );
		}
		
		curr.first -= 1;
		swap( curr.second[NX*y+x], curr.second[NX*ny+nx] );
	    }
	}
    }
    return 1000000;
}

int main() {

    vector<int> s(SIZE);
    for ( int i=0; i<SIZE; ++i ) cin >> s[i];

    cout << Solve( s ) << endl;
    
    return 0;
}


### Prompt

Develop a solution in CPP to the problem described below:

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 <map>
#include <set>

constexpr int NX = 3, NY = 3;
constexpr int SIZE = NX*NY;

using namespace std;

typedef pair< int, vector<int> > PuzzleState;

set< vector<int> > visited;

bool IsSolved( const vector<int>& s ) {
    int cnt = s[SIZE-1] == 0 ? 1 : 0;
    for ( int i=0; i<SIZE; ++i ) {
	if ( s[i] == i+1 ) ++cnt;
    }
    return cnt == SIZE;
}

bool IsVisited( const vector<int>& s ) {
    return visited.find( s ) != visited.end();
}

int Solve( const vector<int>& init_s ) {

    const int dx[4] = { -1,  0, 1, 0 };
    const int dy[4] = {  0, -1, 0, 1 };

    queue< PuzzleState > state;
    state.push( make_pair(0, init_s) );
    visited.insert( init_s );

    while ( !state.empty() ) {

	PuzzleState curr = state.front();

	if ( IsSolved( curr.second ) ) return curr.first;
	state.pop();
	
	int x, y;
	for ( int i=0; i<SIZE; ++i ) {
	    if ( curr.second[i] == 0 ) {
		x = i%NX;
		y = i/NY;
		break;
	    }
	}

	for ( int i=0; i<4; ++i ) {
	    int nx = x + dx[i];
	    int ny = y + dy[i];
	    if ( nx >= 0 && nx < NX && ny >= 0 && ny < NY ) {

		swap( curr.second[NX*y+x], curr.second[NX*ny+nx] );
		curr.first += 1;
		
		if ( !IsVisited( curr.second ) ) {
		    state.push( curr );
		    visited.insert( curr.second );
		}
		
		curr.first -= 1;
		swap( curr.second[NX*y+x], curr.second[NX*ny+nx] );
	    }
	}
    }
    return 1000000;
}

int main() {

    vector<int> s(SIZE);
    for ( int i=0; i<SIZE; ++i ) cin >> s[i];

    cout << Solve( s ) << endl;
    
    return 0;
}


```