#include<cstdio>
#include<map>
#include<string>
#include<queue>
#include<iostream>
#define N 3
#define N2 9
using namespace std;
static const char c[4] = {'u', 'd', 'l', 'r'};
static const int x[4] = {-1, 1, 0, 0};
static const int y[4] = {0, 0, -1, 1};
struct Puzzle
{
  int f[N2];  int space; // f[] to record number sequence, space to record the location of number '0';
  string path;
  bool operator < (const Puzzle &p) const
  {
    for(int i=0; i<N2; i++)
    {
      if(f[i] == p.f[i])  continue;
      else return f[i] < p.f[i];
    }
    return false;
  }
};

bool istarget(Puzzle p)
{
  for(int i=0; i<N2; i++)
  {
    if(p.f[i] == i+1)
      continue;
    else return false;
  }
  return true;
}

string bfs(Puzzle& p)
{
  queue<Puzzle> PQ;
  Puzzle u, v;
  p.path = "";
  map<Puzzle, bool> V;
  V[p] = true;
  PQ.push(p);
  while(!PQ.empty())
  {
    u = PQ.front(); PQ.pop();
    if(istarget(u)) {return u.path;}
    int sx, sy, tx, ty;
    sx = u.space/N; sy = u.space % N;
    for(int r=0; r<4; r++)
    {
      tx = sx + x[r]; ty = sy + y[r];
      if(tx>=N || tx<0 || ty>=N || ty<0) continue;
      v = u; v.space = tx*N + ty;v.path += c[r];
      swap(v.f[sx*N + sy], v.f[tx*N + ty]);

      if(V.find(v) == V.end())
      {
        V[v] = true;PQ.push(v);
      }
    }
  }
  return "unsolvable";
}
int main()
{
  Puzzle input;
  for(int i=0; i<N2; i++)
  {
    scanf("%d", &input.f[i]);
    if(input.f[i] == 0)
    {
      input.f[i] = N2;
      input.space = i;
    }
  }
  string ans = bfs(input);
  cout << ans.size() << endl;
  return 0;
}


### Prompt

Please provide a CPP coded solution 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<cstdio>
#include<map>
#include<string>
#include<queue>
#include<iostream>
#define N 3
#define N2 9
using namespace std;
static const char c[4] = {'u', 'd', 'l', 'r'};
static const int x[4] = {-1, 1, 0, 0};
static const int y[4] = {0, 0, -1, 1};
struct Puzzle
{
  int f[N2];  int space; // f[] to record number sequence, space to record the location of number '0';
  string path;
  bool operator < (const Puzzle &p) const
  {
    for(int i=0; i<N2; i++)
    {
      if(f[i] == p.f[i])  continue;
      else return f[i] < p.f[i];
    }
    return false;
  }
};

bool istarget(Puzzle p)
{
  for(int i=0; i<N2; i++)
  {
    if(p.f[i] == i+1)
      continue;
    else return false;
  }
  return true;
}

string bfs(Puzzle& p)
{
  queue<Puzzle> PQ;
  Puzzle u, v;
  p.path = "";
  map<Puzzle, bool> V;
  V[p] = true;
  PQ.push(p);
  while(!PQ.empty())
  {
    u = PQ.front(); PQ.pop();
    if(istarget(u)) {return u.path;}
    int sx, sy, tx, ty;
    sx = u.space/N; sy = u.space % N;
    for(int r=0; r<4; r++)
    {
      tx = sx + x[r]; ty = sy + y[r];
      if(tx>=N || tx<0 || ty>=N || ty<0) continue;
      v = u; v.space = tx*N + ty;v.path += c[r];
      swap(v.f[sx*N + sy], v.f[tx*N + ty]);

      if(V.find(v) == V.end())
      {
        V[v] = true;PQ.push(v);
      }
    }
  }
  return "unsolvable";
}
int main()
{
  Puzzle input;
  for(int i=0; i<N2; i++)
  {
    scanf("%d", &input.f[i]);
    if(input.f[i] == 0)
    {
      input.f[i] = N2;
      input.space = i;
    }
  }
  string ans = bfs(input);
  cout << ans.size() << endl;
  return 0;
}


```