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

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int,mat> P;

bool check(mat A){
  
  string ans = "123456780";
  string s;
  
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++) s += (char)( A[i][j] + '0' );
  }
  
  return ans == s;  
}

int bfs(mat s){
  
  queue<P> Q;
  map<mat,int> memo;
  
  Q.push( P( 0, s ) );
  memo[ s ] = 0;
  
  while( !Q.empty() ){
    
    P t = Q.front(); Q.pop();
    
    int cost = t.first;
    mat A = t.second;
    
    if( check( A ) == true ) return cost;
    
    int y, x;
    
    for(int i=0;i<3;i++){
      
      for(int j=0;j<3;j++){
	
	if( A[i][j] == 0 ) y = i, x = j;
	
      }
      
    }
    
    int dy[4] = {-1,0,1,0};
    int dx[4] = {0,1,0,-1};
    
    for(int i=0;i<4;i++){
      
      int ny = y + dy[i], nx = x + dx[i];
      
      if( ny < 0 || nx < 0 || 3 <= ny || 3 <= nx ) continue;
      
      mat nA = A;
      int ncost = cost + 1;
      
      swap( nA[y][x], nA[ny][nx] );
      
      if( memo.count( nA ) ) continue;
      
      memo[nA] = ncost;
      Q.push( P( ncost, nA ) );
      
    }
    
  }
  
  return 0; 
}

signed main(){
  
  mat s = mat( 3, vec( 3 ) );
  
  for(int i=0;i<3;i++){
    
    for(int j=0;j<3;j++){
      
      cin>>s[i][j];
      
    }
    
  }
  
  cout<<bfs(s)<<endl;
  
  return 0;
}


### Prompt

In cpp, your task is to solve 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 <bits/stdc++.h>
#define int long long
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int,mat> P;

bool check(mat A){
  
  string ans = "123456780";
  string s;
  
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++) s += (char)( A[i][j] + '0' );
  }
  
  return ans == s;  
}

int bfs(mat s){
  
  queue<P> Q;
  map<mat,int> memo;
  
  Q.push( P( 0, s ) );
  memo[ s ] = 0;
  
  while( !Q.empty() ){
    
    P t = Q.front(); Q.pop();
    
    int cost = t.first;
    mat A = t.second;
    
    if( check( A ) == true ) return cost;
    
    int y, x;
    
    for(int i=0;i<3;i++){
      
      for(int j=0;j<3;j++){
	
	if( A[i][j] == 0 ) y = i, x = j;
	
      }
      
    }
    
    int dy[4] = {-1,0,1,0};
    int dx[4] = {0,1,0,-1};
    
    for(int i=0;i<4;i++){
      
      int ny = y + dy[i], nx = x + dx[i];
      
      if( ny < 0 || nx < 0 || 3 <= ny || 3 <= nx ) continue;
      
      mat nA = A;
      int ncost = cost + 1;
      
      swap( nA[y][x], nA[ny][nx] );
      
      if( memo.count( nA ) ) continue;
      
      memo[nA] = ncost;
      Q.push( P( ncost, nA ) );
      
    }
    
  }
  
  return 0; 
}

signed main(){
  
  mat s = mat( 3, vec( 3 ) );
  
  for(int i=0;i<3;i++){
    
    for(int j=0;j<3;j++){
      
      cin>>s[i][j];
      
    }
    
  }
  
  cout<<bfs(s)<<endl;
  
  return 0;
}


```