#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
typedef pair<vector<int>, int> P;
map<vector<int>, int> checked;
queue<P> que;
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  vector<int> v;
  FOR(i,0,9){
    int n;
    cin>>n;
    v.push_back(n);
  }
  vector<int> goal = {1,2,3,4,5,6,7,8,0};
  que.push(P(v, 0));
  checked[v] = 0;
  while(!que.empty()){
    P p = que.front();
    que.pop();
    vector<int> now = p.first;
    int dist = p.second;
    bool ok = true;
    FOR(i,0,9){
      if(now[i]!=goal[i]){
        ok = false;
        break;
      }
    }
    if(ok){
      cout << dist << endl;
      return 0;
    }
    int x, y, zero;
    FOR(i,0,9){
      if(now[i]==0){
        x = i % 3;
        y = i / 3;
        zero = i;
        break;
      }
    }
    FOR(i,0,4){
      int ny = y + dy[i];
      int nx = x + dx[i];
      if(ny<0||ny>=3||nx<0||nx>=3) continue;
      int j = 3 * ny + nx;
      vector<int> nxt = now;
      swap(nxt[zero], nxt[j]);
      if(checked.count(nxt)==0||checked[nxt] > dist + 1) {
        checked[nxt] = dist + 1;
        que.push(P(nxt, dist+1));
      }
    }
  }
}

### 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 <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
typedef pair<vector<int>, int> P;
map<vector<int>, int> checked;
queue<P> que;
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  vector<int> v;
  FOR(i,0,9){
    int n;
    cin>>n;
    v.push_back(n);
  }
  vector<int> goal = {1,2,3,4,5,6,7,8,0};
  que.push(P(v, 0));
  checked[v] = 0;
  while(!que.empty()){
    P p = que.front();
    que.pop();
    vector<int> now = p.first;
    int dist = p.second;
    bool ok = true;
    FOR(i,0,9){
      if(now[i]!=goal[i]){
        ok = false;
        break;
      }
    }
    if(ok){
      cout << dist << endl;
      return 0;
    }
    int x, y, zero;
    FOR(i,0,9){
      if(now[i]==0){
        x = i % 3;
        y = i / 3;
        zero = i;
        break;
      }
    }
    FOR(i,0,4){
      int ny = y + dy[i];
      int nx = x + dx[i];
      if(ny<0||ny>=3||nx<0||nx>=3) continue;
      int j = 3 * ny + nx;
      vector<int> nxt = now;
      swap(nxt[zero], nxt[j]);
      if(checked.count(nxt)==0||checked[nxt] > dist + 1) {
        checked[nxt] = dist + 1;
        que.push(P(nxt, dist+1));
      }
    }
  }
}

```