#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
using namespace std;

const int N = 3;
const int N2 = 9;
const int mx[4] = {0,-1,0,1};
const int my[4] = {-1,0,1,0};
const char itoc[10] = {'0','1','2','3','4','5','6','7','8','9'};

int bfs(vector<int> p, string key) {
    queue< pair<vector<int>,int> > q;
    map<string,bool> m;
    pair<vector<int>,int> a,b;
    q.push(make_pair(p,0));
    m[key] = true;

    while(!q.empty()) {
        a = q.front(); q.pop();
        bool flg=true;
        int blank;
        for(int i=0; i<N2; i++) {
            if(a.first[i]!=i+1) flg = false;
            if(a.first[i]==N2) blank=i;
        }
        if(flg==true) return a.second;
        int bx = blank%N, by = blank/N;
        for(int i=0; i<4; i++) {
            int x=bx+mx[i],y=by+my[i];
            if(x<0 || x>=N || y<0 || y>=N) continue;
            b = make_pair(a.first,a.second);
            swap(b.first[y*N+x],b.first[blank]);
            key="";
            for(int j=0; j<N2; j++) key += itoc[b.first[j]];
            if(!m[key]) {
                m[key] = true;
                b.second+=1;;
                q.push(b);
            }
        }


    }
    return 0;
}

int main() {
    vector<int> init; int k;
    string key="";
    for(int i=0; i<N2; i++) {
        cin >> k; init.push_back(k);
        if(init[i]==0) init[i]=N2;
        key+=itoc[init[i]];
    }
    cout << bfs(init, key) << endl;
    return 0;
}


### 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<vector>
#include<string>
#include<queue>
#include<map>
using namespace std;

const int N = 3;
const int N2 = 9;
const int mx[4] = {0,-1,0,1};
const int my[4] = {-1,0,1,0};
const char itoc[10] = {'0','1','2','3','4','5','6','7','8','9'};

int bfs(vector<int> p, string key) {
    queue< pair<vector<int>,int> > q;
    map<string,bool> m;
    pair<vector<int>,int> a,b;
    q.push(make_pair(p,0));
    m[key] = true;

    while(!q.empty()) {
        a = q.front(); q.pop();
        bool flg=true;
        int blank;
        for(int i=0; i<N2; i++) {
            if(a.first[i]!=i+1) flg = false;
            if(a.first[i]==N2) blank=i;
        }
        if(flg==true) return a.second;
        int bx = blank%N, by = blank/N;
        for(int i=0; i<4; i++) {
            int x=bx+mx[i],y=by+my[i];
            if(x<0 || x>=N || y<0 || y>=N) continue;
            b = make_pair(a.first,a.second);
            swap(b.first[y*N+x],b.first[blank]);
            key="";
            for(int j=0; j<N2; j++) key += itoc[b.first[j]];
            if(!m[key]) {
                m[key] = true;
                b.second+=1;;
                q.push(b);
            }
        }


    }
    return 0;
}

int main() {
    vector<int> init; int k;
    string key="";
    for(int i=0; i<N2; i++) {
        cin >> k; init.push_back(k);
        if(init[i]==0) init[i]=N2;
        key+=itoc[init[i]];
    }
    cout << bfs(init, key) << endl;
    return 0;
}


```