#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <queue>

using namespace std;

#define N 3
#define N2 9

struct Puzzle {
  int field[N2];
  int blank;
  int count;

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

bool isTrue(Puzzle p);
int bfs(Puzzle s);

int x[4] = {-1, 0, 1, 0};
int y[4] = {0, -1, 0, 1};

int main() {
  Puzzle input;
  int i;

  for (i = 0; i < N2; i++) {
    cin >> input.field[i];
    if (input.field[i] == 0) {
      input.field[i] = N2;
      input.blank = i;
    }
  }

  cout << bfs(input) << endl;

  return 0;
}

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

int bfs(Puzzle s) {
  queue<Puzzle> Q;
  map<Puzzle, bool> V;
  Puzzle u, v;
  int x1, y1, x2, y2, i;
  s.count = 0;
  Q.push(s);
  V[s] = true;

  while (!Q.empty()) {
    u = Q.front();
    Q.pop();
    if (isTrue(u)) return u.count;
    x1 = u.blank / N;
    y1 = u.blank % N;
    for (i = 0; i < 4; i++) {
      x2 = x1 + x[i];
      y2 = y1 + y[i];
      if (!(x2 >= 0 && y2 >= 0 && x2 < N && y2 < N)) continue;
      v = u;
      swap(v.field[u.blank], v.field[x2 * N + y2]);
      v.blank = x2 * N + y2;
      if (!V[v]) {
	V[v] = true;
	v.count++;
	Q.push(v);

      }
    }
  }
}


### 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 <cmath>
#include <string>
#include <map>
#include <queue>

using namespace std;

#define N 3
#define N2 9

struct Puzzle {
  int field[N2];
  int blank;
  int count;

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

bool isTrue(Puzzle p);
int bfs(Puzzle s);

int x[4] = {-1, 0, 1, 0};
int y[4] = {0, -1, 0, 1};

int main() {
  Puzzle input;
  int i;

  for (i = 0; i < N2; i++) {
    cin >> input.field[i];
    if (input.field[i] == 0) {
      input.field[i] = N2;
      input.blank = i;
    }
  }

  cout << bfs(input) << endl;

  return 0;
}

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

int bfs(Puzzle s) {
  queue<Puzzle> Q;
  map<Puzzle, bool> V;
  Puzzle u, v;
  int x1, y1, x2, y2, i;
  s.count = 0;
  Q.push(s);
  V[s] = true;

  while (!Q.empty()) {
    u = Q.front();
    Q.pop();
    if (isTrue(u)) return u.count;
    x1 = u.blank / N;
    y1 = u.blank % N;
    for (i = 0; i < 4; i++) {
      x2 = x1 + x[i];
      y2 = y1 + y[i];
      if (!(x2 >= 0 && y2 >= 0 && x2 < N && y2 < N)) continue;
      v = u;
      swap(v.field[u.blank], v.field[x2 * N + y2]);
      v.blank = x2 * N + y2;
      if (!V[v]) {
	V[v] = true;
	v.count++;
	Q.push(v);

      }
    }
  }
}


```