#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

struct Puzzle{
  int field[9];
  int space;
  int turn;

  bool operator < (const Puzzle& a) const{
    rep(i, 9){
      if(a.field[i] == field[i]) continue;
      return field[i] >  a.field[i];
    }
    return false;
  }
};

bool check(Puzzle p){
  rep(i, 9){
    if(p.field[i] != i+1) return false;
  }
  return true;
}

int solve(Puzzle in){
  queue<Puzzle> q;  
  map<Puzzle, bool> mp;

  q.push(in);
  mp[in] = true;
  
  // bfs
  while(!q.empty()){
    Puzzle p = q.front(); q.pop();
    if(check(p)) return p.turn;
    int x = p.space % 3;
    int y = p.space / 3;
    rep(i, 4){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx < 0 || 2 < nx || ny < 0 || 2 < ny) continue;
      Puzzle tmp = p;
      swap(tmp.field[p.space], tmp.field[3 * ny + nx]);
      tmp.space = 3 * ny + nx;
      if(mp[tmp] == false){
    mp[tmp] = true;
    tmp.turn++;
    q.push(tmp);
      }
    }
  }
  return -1;
}

signed main(){
  Puzzle in;
  
  rep(i, 9){
    cin >> in.field[i];
    if(in.field[i] == 0){
      in.field[i] = 9;
      in.space = i;
    }    
  }

  in.turn = 0;
  cout << solve(in) << endl;
}
### Prompt

Please create a solution in CPP 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<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

struct Puzzle{
  int field[9];
  int space;
  int turn;

  bool operator < (const Puzzle& a) const{
    rep(i, 9){
      if(a.field[i] == field[i]) continue;
      return field[i] >  a.field[i];
    }
    return false;
  }
};

bool check(Puzzle p){
  rep(i, 9){
    if(p.field[i] != i+1) return false;
  }
  return true;
}

int solve(Puzzle in){
  queue<Puzzle> q;  
  map<Puzzle, bool> mp;

  q.push(in);
  mp[in] = true;
  
  // bfs
  while(!q.empty()){
    Puzzle p = q.front(); q.pop();
    if(check(p)) return p.turn;
    int x = p.space % 3;
    int y = p.space / 3;
    rep(i, 4){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx < 0 || 2 < nx || ny < 0 || 2 < ny) continue;
      Puzzle tmp = p;
      swap(tmp.field[p.space], tmp.field[3 * ny + nx]);
      tmp.space = 3 * ny + nx;
      if(mp[tmp] == false){
    mp[tmp] = true;
    tmp.turn++;
    q.push(tmp);
      }
    }
  }
  return -1;
}

signed main(){
  Puzzle in;
  
  rep(i, 9){
    cin >> in.field[i];
    if(in.field[i] == 0){
      in.field[i] = 9;
      in.space = i;
    }    
  }

  in.turn = 0;
  cout << solve(in) << endl;
}
```