#include<iostream>
#include<map>
#include<queue>
#define N 9

using namespace std;

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

struct Puzzle{
  int field[N];
  int blank;
  int num;

  bool operator < (const Puzzle& a) const{
    for(int i = 0; i < N; i++){
      if(a.field[i] == field[i]) continue;
      return field[i] >  a.field[i];
    }
    return false;
  }
};

bool check(Puzzle puz){
  for(int i = 0; i < N; i++){
    if(puz.field[i] != i+1) return false;
  }
  return true;
}

int bfs(Puzzle puz){
  queue<Puzzle> que;
  map<Puzzle, bool> mp;

  que.push(puz);
  mp[puz] = true;

  while(!que.empty()){
    Puzzle p = que.front(); que.pop();
    if(check(p) == true) return p.num;
    int x = p.blank % 3;
    int y = p.blank / 3;
    for(int i = 0; i < 4; i++){
      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.blank], tmp.field[3 * ny + nx]);
      tmp.blank = 3 * ny + nx;
      if(mp[tmp] == false){
    mp[tmp] = true;
    tmp.num++;
    que.push(tmp);
      }
    }
  }
  return -1;
}

signed main(){
  Puzzle puz;

  for(int i = 0; i < N; i++){
    cin >> puz.field[i];
    if(puz.field[i] == 0){
      puz.field[i] = N;
      puz.blank = i;
    }
  }

  puz.num = 0;
  int b = bfs(puz);
  cout << b << endl;
}


### Prompt

Create a solution in CPP for 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<iostream>
#include<map>
#include<queue>
#define N 9

using namespace std;

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

struct Puzzle{
  int field[N];
  int blank;
  int num;

  bool operator < (const Puzzle& a) const{
    for(int i = 0; i < N; i++){
      if(a.field[i] == field[i]) continue;
      return field[i] >  a.field[i];
    }
    return false;
  }
};

bool check(Puzzle puz){
  for(int i = 0; i < N; i++){
    if(puz.field[i] != i+1) return false;
  }
  return true;
}

int bfs(Puzzle puz){
  queue<Puzzle> que;
  map<Puzzle, bool> mp;

  que.push(puz);
  mp[puz] = true;

  while(!que.empty()){
    Puzzle p = que.front(); que.pop();
    if(check(p) == true) return p.num;
    int x = p.blank % 3;
    int y = p.blank / 3;
    for(int i = 0; i < 4; i++){
      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.blank], tmp.field[3 * ny + nx]);
      tmp.blank = 3 * ny + nx;
      if(mp[tmp] == false){
    mp[tmp] = true;
    tmp.num++;
    que.push(tmp);
      }
    }
  }
  return -1;
}

signed main(){
  Puzzle puz;

  for(int i = 0; i < N; i++){
    cin >> puz.field[i];
    if(puz.field[i] == 0){
      puz.field[i] = N;
      puz.blank = i;
    }
  }

  puz.num = 0;
  int b = bfs(puz);
  cout << b << endl;
}


```