#include<stdio.h>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
#define maxn 10
struct my
{
    int tu[10];
    int space;
    int  ans;
    bool operator <(const my &p)const{
    for (int i=0;i<9;i++)
        {
            if(tu[i]==p.tu[i]) continue;
        return tu[i]>p.tu[i];
        }
        return false ;
    }
};
bool is(my s)
{
    for (int i=0;i<9;i++)
        if(s.tu[i]!=(i+1)) return false;
    return true;
}
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
//char dir[]={'u','l','d','r'};
int bfs(my s)
{
    queue<my>Q;
    map<my,bool>V;
    s.ans=0;
    Q.push(s);
    V[s]=true;
    my u,v;

    while(!Q.empty())
    {
        u=Q.front();
        Q.pop();
        if(is(u)) return u.ans;
        int sx=u.space/3;
        int sy=u.space%3;
        for (int i=0;i<4;i++)
        {
            int tx=sx+dx[i];
            int ty=sy+dy[i];
            if(tx<0||ty<0||tx>=3||ty>=3) continue;
            v=u;
            swap(v.tu[u.space],v.tu[tx*3+ty]);
            v.space=tx*3+ty;
            if(!V[v])
            {
                V[v]=true;
                v.ans++;
                Q.push(v);
            }
        }
    }
}
int main()
{
    my in;
    for (int i=0;i<9;i++)
    {
        scanf("%d",&in.tu[i]);
        if(in.tu[i]==0){
            in.space=i;
            in.tu[i]=9;
        }
    }
    int sum=bfs(in);
    printf("%d\n",sum);
    return 0;
}
### Prompt

Create a solution in cpp for 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<stdio.h>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
#define maxn 10
struct my
{
    int tu[10];
    int space;
    int  ans;
    bool operator <(const my &p)const{
    for (int i=0;i<9;i++)
        {
            if(tu[i]==p.tu[i]) continue;
        return tu[i]>p.tu[i];
        }
        return false ;
    }
};
bool is(my s)
{
    for (int i=0;i<9;i++)
        if(s.tu[i]!=(i+1)) return false;
    return true;
}
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
//char dir[]={'u','l','d','r'};
int bfs(my s)
{
    queue<my>Q;
    map<my,bool>V;
    s.ans=0;
    Q.push(s);
    V[s]=true;
    my u,v;

    while(!Q.empty())
    {
        u=Q.front();
        Q.pop();
        if(is(u)) return u.ans;
        int sx=u.space/3;
        int sy=u.space%3;
        for (int i=0;i<4;i++)
        {
            int tx=sx+dx[i];
            int ty=sy+dy[i];
            if(tx<0||ty<0||tx>=3||ty>=3) continue;
            v=u;
            swap(v.tu[u.space],v.tu[tx*3+ty]);
            v.space=tx*3+ty;
            if(!V[v])
            {
                V[v]=true;
                v.ans++;
                Q.push(v);
            }
        }
    }
}
int main()
{
    my in;
    for (int i=0;i<9;i++)
    {
        scanf("%d",&in.tu[i]);
        if(in.tu[i]==0){
            in.space=i;
            in.tu[i]=9;
        }
    }
    int sum=bfs(in);
    printf("%d\n",sum);
    return 0;
}
```