#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define REPR(i, m, n) for (int i = (int)(m); i >= (int)(n); i--)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1001001001;
typedef unsigned long long ll;

struct Puzzle{
  int f[9];
  int space;
  int cnt;

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

queue<Puzzle> Q;
map<Puzzle, bool> V;

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

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

int main(){
  Puzzle in;

  rep(i, 9){
    cin >> in.f[i];
    if(in.f[i] == 0){
      in.f[i] = 9;
      in.space = i;
    }
  }
  in.cnt = 0;

  V[in] = true;
  Q.push(in);
  int ans;
  while(!Q.empty()){
    Puzzle u = Q.front(); Q.pop();
    if(isTarget(u)){
      ans = u.cnt;
      break;
    } 
    int sx = u.space / 3;
    int sy = u.space % 3;
    rep(i, 4){
      int tx = sx + dx[i];
      int ty = sy + dy[i];
      if(tx<0 || ty<0 || 3<=tx || 3<=ty) continue;
      Puzzle v = u;
      v.space = tx * 3 + ty;
      swap(v.f[u.space], v.f[v.space]);
      v.cnt++;
      if(!V[v]){
        V[v] = true;
        Q.push(v);
      }
    }
  }

  cout << ans << endl;

  return 0;
}




### Prompt

Develop a solution in CPP to the problem described below:

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 rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define REPR(i, m, n) for (int i = (int)(m); i >= (int)(n); i--)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1001001001;
typedef unsigned long long ll;

struct Puzzle{
  int f[9];
  int space;
  int cnt;

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

queue<Puzzle> Q;
map<Puzzle, bool> V;

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

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

int main(){
  Puzzle in;

  rep(i, 9){
    cin >> in.f[i];
    if(in.f[i] == 0){
      in.f[i] = 9;
      in.space = i;
    }
  }
  in.cnt = 0;

  V[in] = true;
  Q.push(in);
  int ans;
  while(!Q.empty()){
    Puzzle u = Q.front(); Q.pop();
    if(isTarget(u)){
      ans = u.cnt;
      break;
    } 
    int sx = u.space / 3;
    int sy = u.space % 3;
    rep(i, 4){
      int tx = sx + dx[i];
      int ty = sy + dy[i];
      if(tx<0 || ty<0 || 3<=tx || 3<=ty) continue;
      Puzzle v = u;
      v.space = tx * 3 + ty;
      swap(v.f[u.space], v.f[v.space]);
      v.cnt++;
      if(!V[v]){
        V[v] = true;
        Q.push(v);
      }
    }
  }

  cout << ans << endl;

  return 0;
}




```