#include <bits/stdc++.h>
using namespace std;
#define N 3
#define N2 9
struct puzzle{
    int f[N2];
    int space;
    string path;

    /*bool operator == (const puzzle &t1) const {
        for(int i=0;i<N2;++i){
            if(f[i] != t1.f[i]) return false;
        }
        return true;
    }*/
    bool operator < (const puzzle &t1) const {
        for(int i=0;i<N2;++i){
            if(f[i] == t1.f[i]) continue;
            return f[i] > t1.f[i];
        }
        return false;
    }
};

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

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

string bfs(puzzle init){
    map<puzzle,bool> m;
    m[init] = true;
    queue<puzzle> q;
    q.push(init);
    puzzle u, v;
    int sx, sy, tx, ty;
    while(!q.empty()){
        u = q.front();
        q.pop();
        if(target(u)) return u.path;
        tx = u.space/N;
        ty = u.space%N;
        for(int i=0;i<4;++i){
            sx = tx + dx[i];
            sy = ty + dy[i];
            if(sx<0 || sy<0 || sx>=N || sy>=N) continue;
            v = u;
            v.space = sx*N+sy;
            swap(v.f[u.space],v.f[v.space]);
            if(!m[v]){
                m[v] = true;
                v.path += dstr[i];
                q.push(v);
            }
        }
    }
}


int main(){
    puzzle init;
    init.path = "";
    for(int i=0;i<N2;++i){
        cin>>init.f[i];
        if(init.f[i]==0){
            init.f[i] = N2;
            init.space = i;
        }
    }
    string res = bfs(init);
    cout<<res.size()<<endl;
    return 0;
}


### Prompt

Please provide a Cpp coded solution 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 <bits/stdc++.h>
using namespace std;
#define N 3
#define N2 9
struct puzzle{
    int f[N2];
    int space;
    string path;

    /*bool operator == (const puzzle &t1) const {
        for(int i=0;i<N2;++i){
            if(f[i] != t1.f[i]) return false;
        }
        return true;
    }*/
    bool operator < (const puzzle &t1) const {
        for(int i=0;i<N2;++i){
            if(f[i] == t1.f[i]) continue;
            return f[i] > t1.f[i];
        }
        return false;
    }
};

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

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

string bfs(puzzle init){
    map<puzzle,bool> m;
    m[init] = true;
    queue<puzzle> q;
    q.push(init);
    puzzle u, v;
    int sx, sy, tx, ty;
    while(!q.empty()){
        u = q.front();
        q.pop();
        if(target(u)) return u.path;
        tx = u.space/N;
        ty = u.space%N;
        for(int i=0;i<4;++i){
            sx = tx + dx[i];
            sy = ty + dy[i];
            if(sx<0 || sy<0 || sx>=N || sy>=N) continue;
            v = u;
            v.space = sx*N+sy;
            swap(v.f[u.space],v.f[v.space]);
            if(!m[v]){
                m[v] = true;
                v.path += dstr[i];
                q.push(v);
            }
        }
    }
}


int main(){
    puzzle init;
    init.path = "";
    for(int i=0;i<N2;++i){
        cin>>init.f[i];
        if(init.f[i]==0){
            init.f[i] = N2;
            init.space = i;
        }
    }
    string res = bfs(init);
    cout<<res.size()<<endl;
    return 0;
}


```