#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int c[4][2]={1,0,0,1,-1,0,0,-1};
int puzzle[10];

map<string,int> book;
struct yun
{
    int s;
    int state[9];
};

int bfs()
{
    int i,j,k,l;
    yun st,en;
    queue<yun> Q;
    st.s=0;
    for(i=0;i<9;i++)
        st.state[i]=puzzle[i];
    Q.push(st);
    while(Q.size())
    {
        st=Q.front();
        Q.pop();
        for(k=0;k<9;k++)
            if(!st.state[k])break;
        int x=k/3,y=k%3;
        for(j=0;j<4;j++)
        {
            int dx=x+c[j][0];
            int dy=y+c[j][1];
            int dz=dx*3+dy;
            if(dx<0||dy<0||dx>=3||dy>=3)continue;
            string ss="";
            for(l=0;l<9;l++)
                en.state[l]=st.state[l];
            en.state[k]=en.state[dz];
            en.state[dz]=0;
            int f=0;
            for(l=0;l<8;l++)
            {
                ss+=en.state[l]+'0';
                if(en.state[l]!=l+1)
                    f=1;
            }
          //  cout<<ss<<endl;
            if(!f)return st.s+1;
            if(book[ss])continue;
            book[ss]=1;
            en.s=st.s+1;
            Q.push(en);
        }
    }
}

int main()
{
    int i;
    for(i=0;i<9;i++)
        scanf("%d",&puzzle[i]);
    int g=0;
    for(i=0;i<8;i++)
    {
        if(puzzle[i]!=i+1)
            g=1;
    }
    int max1;
    if(!g)
        max1=0;
    else max1=bfs();
    printf("%d\n",max1);
}


### Prompt

Your challenge is to write 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<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int c[4][2]={1,0,0,1,-1,0,0,-1};
int puzzle[10];

map<string,int> book;
struct yun
{
    int s;
    int state[9];
};

int bfs()
{
    int i,j,k,l;
    yun st,en;
    queue<yun> Q;
    st.s=0;
    for(i=0;i<9;i++)
        st.state[i]=puzzle[i];
    Q.push(st);
    while(Q.size())
    {
        st=Q.front();
        Q.pop();
        for(k=0;k<9;k++)
            if(!st.state[k])break;
        int x=k/3,y=k%3;
        for(j=0;j<4;j++)
        {
            int dx=x+c[j][0];
            int dy=y+c[j][1];
            int dz=dx*3+dy;
            if(dx<0||dy<0||dx>=3||dy>=3)continue;
            string ss="";
            for(l=0;l<9;l++)
                en.state[l]=st.state[l];
            en.state[k]=en.state[dz];
            en.state[dz]=0;
            int f=0;
            for(l=0;l<8;l++)
            {
                ss+=en.state[l]+'0';
                if(en.state[l]!=l+1)
                    f=1;
            }
          //  cout<<ss<<endl;
            if(!f)return st.s+1;
            if(book[ss])continue;
            book[ss]=1;
            en.s=st.s+1;
            Q.push(en);
        }
    }
}

int main()
{
    int i;
    for(i=0;i<9;i++)
        scanf("%d",&puzzle[i]);
    int g=0;
    for(i=0;i<8;i++)
    {
        if(puzzle[i]!=i+1)
            g=1;
    }
    int max1;
    if(!g)
        max1=0;
    else max1=bfs();
    printf("%d\n",max1);
}


```