#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
const double PI = acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;

int main() {
  Graph board(3, vector<int>(3)),last(3, vector<int>(3));
  rep(i,3) {
    rep(j,3) cin >> board[i][j];
  }

  last = {
    {1,2,3},
    {4,5,6},
    {7,8,0}
  };

  map<Graph, int> m;
  m[board] = 0;
  queue <Graph> que;
  que.push(board);

  const vector<int> dy = {-1,0,0,1};
  const vector<int> dx = {0,-1,1,0};

  while(!que.empty()) {
    Graph v = que.front();
    int count = m[v];
    que.pop();
    int y,x;
    rep(i,3) {
      rep(j,3) {
        if (v[i][j] == 0) {
          y = i;
          x = j;
        }
      }
    }

    rep(i,4) {
      int yy = y + dy[i];
      int xx = x + dx[i];
      if (yy < 0 || yy >= 3 || xx < 0 || xx >= 3) continue;
      swap(v[y][x],v[yy][xx]);
      if (!m.count(v)) {
        que.push(v);
        m[v] = count + 1;
        if (m.count(last)) goto OUT;
      }
      swap(v[y][x],v[yy][xx]);
    }
  }

  OUT:

  cout << m[last] << endl;
}

### Prompt

Your task is to create a Cpp solution 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
const double PI = acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;

int main() {
  Graph board(3, vector<int>(3)),last(3, vector<int>(3));
  rep(i,3) {
    rep(j,3) cin >> board[i][j];
  }

  last = {
    {1,2,3},
    {4,5,6},
    {7,8,0}
  };

  map<Graph, int> m;
  m[board] = 0;
  queue <Graph> que;
  que.push(board);

  const vector<int> dy = {-1,0,0,1};
  const vector<int> dx = {0,-1,1,0};

  while(!que.empty()) {
    Graph v = que.front();
    int count = m[v];
    que.pop();
    int y,x;
    rep(i,3) {
      rep(j,3) {
        if (v[i][j] == 0) {
          y = i;
          x = j;
        }
      }
    }

    rep(i,4) {
      int yy = y + dy[i];
      int xx = x + dx[i];
      if (yy < 0 || yy >= 3 || xx < 0 || xx >= 3) continue;
      swap(v[y][x],v[yy][xx]);
      if (!m.count(v)) {
        que.push(v);
        m[v] = count + 1;
        if (m.count(last)) goto OUT;
      }
      swap(v[y][x],v[yy][xx]);
    }
  }

  OUT:

  cout << m[last] << endl;
}

```