#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
  
using namespace std;
  
#define RY 3
#define N 9
  
typedef struct board {
  int O[N];
  int ling;
  vector<int> path;
  
  bool operator < (const board &t) const {
    for (int i = 0; i < N; i++) {
      if (O[i] == t.O[i]) continue;
      else if (O[i] < t.O[i]) return true;
      else return false;
    }
    return false;
  }
} cubic;
 
int xx[4] = { 0, 1, 0, -1 };
int yy[4] = { 1, 0, -1, 0 };
  
bool fingoal(cubic b) {
  for (int i = 0; i < N-1; i ++)
    if (b.O[i] != i+1) return false;
  
  return true;
}
  
void meltd(cubic b) {
  map<cubic, bool> visited;
  queue<cubic> q;
  q.push(b);
  
  while (!q.empty()) {
    cubic bcur = q.front(); q.pop();
    visited[bcur] = true;
  
    if (fingoal(bcur)) {
      cout << bcur.path.size() << endl;
      return;
    }
  
    for (int i = 0; i < 4; i ++) {
      cubic b = bcur;
      int nx = (bcur.ling / RY) + xx[i];
      int ny = (bcur.ling % RY) + yy[i];
  
      if (nx < 0 || nx > 2 || ny < 0 || ny > 2) continue;
  
      b.ling = nx * RY + ny;
      swap(b.O[b.ling], b.O[bcur.ling]);
  
      if (visited[b]) continue;
  
      b.path.push_back(b.ling);
      q.push(b);
    }
  }
}
  
int main() {
  cubic b;
  
  for (int i = 0; i < N; i++) {
    cin >> b.O[i];
    if (b.O[i] == 0) b.ling = i;
  }
  
  meltd(b);
}
### Prompt

Construct a CPP code solution to the problem outlined:

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 <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
  
using namespace std;
  
#define RY 3
#define N 9
  
typedef struct board {
  int O[N];
  int ling;
  vector<int> path;
  
  bool operator < (const board &t) const {
    for (int i = 0; i < N; i++) {
      if (O[i] == t.O[i]) continue;
      else if (O[i] < t.O[i]) return true;
      else return false;
    }
    return false;
  }
} cubic;
 
int xx[4] = { 0, 1, 0, -1 };
int yy[4] = { 1, 0, -1, 0 };
  
bool fingoal(cubic b) {
  for (int i = 0; i < N-1; i ++)
    if (b.O[i] != i+1) return false;
  
  return true;
}
  
void meltd(cubic b) {
  map<cubic, bool> visited;
  queue<cubic> q;
  q.push(b);
  
  while (!q.empty()) {
    cubic bcur = q.front(); q.pop();
    visited[bcur] = true;
  
    if (fingoal(bcur)) {
      cout << bcur.path.size() << endl;
      return;
    }
  
    for (int i = 0; i < 4; i ++) {
      cubic b = bcur;
      int nx = (bcur.ling / RY) + xx[i];
      int ny = (bcur.ling % RY) + yy[i];
  
      if (nx < 0 || nx > 2 || ny < 0 || ny > 2) continue;
  
      b.ling = nx * RY + ny;
      swap(b.O[b.ling], b.O[bcur.ling]);
  
      if (visited[b]) continue;
  
      b.path.push_back(b.ling);
      q.push(b);
    }
  }
}
  
int main() {
  cubic b;
  
  for (int i = 0; i < N; i++) {
    cin >> b.O[i];
    if (b.O[i] == 0) b.ling = i;
  }
  
  meltd(b);
}
```