#include<bits/stdc++.h>
using namespace std;

#define N 3
#define LIM 32
#define HN 362897

struct dep{
  int depth,key;
};

int ans[N][N]={
  {1,2,3},
  {4,5,6},
  {7,8,0}
};

int mins = LIM;
struct dep h[HN];

int hash1(int k){
    return k%HN;
}
int hash2(int k){
  return 1+k%(HN-1);
}
int hashs(int k, int i){
  return (hash1(k)+i*hash2(k))%HN;
}


void dfs(int X[N][N], int n){
  int i,j,in,jn,a=0,b=1;
  int f=0;
  int tmp[N][N];
  for(i=0;i<N;i++)
  {
    for(j=0;j<N;j++)
    {
      if(ans[i][j]!=X[i][j])f++;
      if(X[i][j]==0){
        in=i;
        jn=j;
      }
      a+=X[i][j]*b;
      b*=10;
    }
  }

  if(f==0){
    if(mins>=n)mins=n;
    return;
  }
  if(n>mins)return;
  i=0;
  while(1){
    b=hashs(a, i);
    if(h[b].key == 0){
      h[b].key=a;
      h[b].depth=n;
      break;
    }else if(h[b].key == a){
      if(h[b].depth>n){
        h[b].depth=n;
        break;
      }else return;
    }
    i++;
  }

  if(in>0 && in<N){
    memcpy(tmp,X,sizeof(int)*N*N);
    swap(tmp[in][jn],tmp[in-1][jn]);
    dfs(tmp, n+1);
  }
  if(jn>0 && jn<N){
    memcpy(tmp,X,sizeof(int)*N*N);
    swap(tmp[in][jn],tmp[in][jn-1]);
    dfs(tmp, n+1);
  }

  if(in>=0 && in<N-1){
    memcpy(tmp,X,sizeof(int)*N*N);
    swap(tmp[in][jn],tmp[in+1][jn]);
    dfs(tmp, n+1);
  }
  if(jn>=0 && jn<N-1){
    memcpy(tmp,X,sizeof(int)*N*N);
    swap(tmp[in][jn],tmp[in][jn+1]);
    dfs(tmp, n+1);
  }

}

int main(){
  int i,j;
  int X[N][N]={};
  for(i=0;i<N;i++)for(j=0;j<N;j++)cin>>X[i][j];
  dfs(X,0);
  cout<<mins<<endl;
  return 0;
}


### Prompt

Construct a Cpp code solution to the problem outlined:

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 LIM 32
#define HN 362897

struct dep{
  int depth,key;
};

int ans[N][N]={
  {1,2,3},
  {4,5,6},
  {7,8,0}
};

int mins = LIM;
struct dep h[HN];

int hash1(int k){
    return k%HN;
}
int hash2(int k){
  return 1+k%(HN-1);
}
int hashs(int k, int i){
  return (hash1(k)+i*hash2(k))%HN;
}


void dfs(int X[N][N], int n){
  int i,j,in,jn,a=0,b=1;
  int f=0;
  int tmp[N][N];
  for(i=0;i<N;i++)
  {
    for(j=0;j<N;j++)
    {
      if(ans[i][j]!=X[i][j])f++;
      if(X[i][j]==0){
        in=i;
        jn=j;
      }
      a+=X[i][j]*b;
      b*=10;
    }
  }

  if(f==0){
    if(mins>=n)mins=n;
    return;
  }
  if(n>mins)return;
  i=0;
  while(1){
    b=hashs(a, i);
    if(h[b].key == 0){
      h[b].key=a;
      h[b].depth=n;
      break;
    }else if(h[b].key == a){
      if(h[b].depth>n){
        h[b].depth=n;
        break;
      }else return;
    }
    i++;
  }

  if(in>0 && in<N){
    memcpy(tmp,X,sizeof(int)*N*N);
    swap(tmp[in][jn],tmp[in-1][jn]);
    dfs(tmp, n+1);
  }
  if(jn>0 && jn<N){
    memcpy(tmp,X,sizeof(int)*N*N);
    swap(tmp[in][jn],tmp[in][jn-1]);
    dfs(tmp, n+1);
  }

  if(in>=0 && in<N-1){
    memcpy(tmp,X,sizeof(int)*N*N);
    swap(tmp[in][jn],tmp[in+1][jn]);
    dfs(tmp, n+1);
  }
  if(jn>=0 && jn<N-1){
    memcpy(tmp,X,sizeof(int)*N*N);
    swap(tmp[in][jn],tmp[in][jn+1]);
    dfs(tmp, n+1);
  }

}

int main(){
  int i,j;
  int X[N][N]={};
  for(i=0;i<N;i++)for(j=0;j<N;j++)cin>>X[i][j];
  dfs(X,0);
  cout<<mins<<endl;
  return 0;
}


```