#include <iostream>
#include <queue>
#include <map>
#define N 3
#define NN 9

using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
char direction[4] = {'u', 'l', 'd', 'r'};

typedef struct Puzzle{
    int state[NN];
    int space;
    string result;

    bool operator < (const Puzzle &p) const{
        for(int i = 0; i < NN; i++){
            if(state[i] == p.state[i]) continue;
            return state[i] > p.state[i];
        }
        return false;
    }
}P;

bool isfinished(P p){
    for(int i = 0; i < NN; i++){
        if(p.state[i] != i+1) return false;
    }
    return true;
}

string bfs(P p){
    queue<P> Q;
    map<P, bool> V;
    P u, v;
    int sx, sy, tx, ty;

    p.result = "";
    Q.push(p);
    V[p] = true;

    while(!Q.empty()){
        u = Q.front();
        Q.pop();

        if(isfinished(u)) return u.result;

        sx = u.space / N;
        sy = u.space % N;
        for(int i = 0; i < 4; i++){
            tx = sx + dx[i];
            ty = sy + dy[i];
            
            if(tx < 0 || ty < 0 || tx >= N || ty >= N) continue;

            v = u;
            int tmp = v.state[u.space];
            v.state[u.space] = v.state[tx * N + ty];
            v.state[tx * N + ty] = tmp;
            v.space = tx * N + ty;

            if(!V[v]){
                V[v] = true;
                v.result += direction[i];
                Q.push(v);
            }
        }
    }
    return "";
}

int main(){
    P p;

    for(int i = 0; i < NN; i++){
        cin >> p.state[i];
        if(p.state[i] == 0){
            p.state[i] = NN;
            p.space = i;
        }
    }

    string result = bfs(p);

    cout << result.size() << endl;

    return 0;
}

### Prompt

Please formulate 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 <queue>
#include <map>
#define N 3
#define NN 9

using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
char direction[4] = {'u', 'l', 'd', 'r'};

typedef struct Puzzle{
    int state[NN];
    int space;
    string result;

    bool operator < (const Puzzle &p) const{
        for(int i = 0; i < NN; i++){
            if(state[i] == p.state[i]) continue;
            return state[i] > p.state[i];
        }
        return false;
    }
}P;

bool isfinished(P p){
    for(int i = 0; i < NN; i++){
        if(p.state[i] != i+1) return false;
    }
    return true;
}

string bfs(P p){
    queue<P> Q;
    map<P, bool> V;
    P u, v;
    int sx, sy, tx, ty;

    p.result = "";
    Q.push(p);
    V[p] = true;

    while(!Q.empty()){
        u = Q.front();
        Q.pop();

        if(isfinished(u)) return u.result;

        sx = u.space / N;
        sy = u.space % N;
        for(int i = 0; i < 4; i++){
            tx = sx + dx[i];
            ty = sy + dy[i];
            
            if(tx < 0 || ty < 0 || tx >= N || ty >= N) continue;

            v = u;
            int tmp = v.state[u.space];
            v.state[u.space] = v.state[tx * N + ty];
            v.state[tx * N + ty] = tmp;
            v.space = tx * N + ty;

            if(!V[v]){
                V[v] = true;
                v.result += direction[i];
                Q.push(v);
            }
        }
    }
    return "";
}

int main(){
    P p;

    for(int i = 0; i < NN; i++){
        cin >> p.state[i];
        if(p.state[i] == 0){
            p.state[i] = NN;
            p.space = i;
        }
    }

    string result = bfs(p);

    cout << result.size() << endl;

    return 0;
}

```