#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <stack>
#include <map>
#include <string>
using namespace std;

#define FLG  INT_MIN
#define GOAL 0

#define N 3

map<string, int> mp;
queue<pair<string, int> > Q;

vector<int> neighbor(int pos)
{
    vector<int> rt;
    if (pos % N != 0)
        rt.push_back(pos - 1);
    if (pos % N != N - 1)
        rt.push_back(pos + 1);
    if (pos - N >= 0)
        rt.push_back(pos - N);
    if (pos + N < N * N)
        rt.push_back(pos + N);
    return rt;
}

int bfs()
{
    string st, tmp;
    int cnt, pos;
    while (!Q.empty()) {
        st = Q.front().first;
        cnt = Q.front().second;
        pos = st.find("0");
        Q.pop();
        if (mp.count(st)) {
            if (mp[st] == FLG) {
                continue;
            } else if (mp[st] == GOAL) {
                return cnt;
            } else
                printf("ERROR: %d\n", __LINE__);
        }
        mp[st] = FLG;
        vector<int> nb(neighbor(pos));
        for (int i = 0; i < nb.size(); i++) {
            tmp = st;
            tmp[pos] = st[nb[i]]; tmp[nb[i]] = st[pos];
            Q.push(make_pair(tmp, cnt + 1));
        }
    }
    return INT_MIN;
}

int main()
{
    string st, gl = "123456780";
    for (int i = 0; i < 9; i++) {
        int  j;
        cin >> j;
        st += to_string(j);
    }
    mp[gl] = GOAL;
    Q.push(make_pair(st, 0));
    cout << bfs() << endl;
    return 0;
}
### Prompt

In cpp, your task is to solve 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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <stack>
#include <map>
#include <string>
using namespace std;

#define FLG  INT_MIN
#define GOAL 0

#define N 3

map<string, int> mp;
queue<pair<string, int> > Q;

vector<int> neighbor(int pos)
{
    vector<int> rt;
    if (pos % N != 0)
        rt.push_back(pos - 1);
    if (pos % N != N - 1)
        rt.push_back(pos + 1);
    if (pos - N >= 0)
        rt.push_back(pos - N);
    if (pos + N < N * N)
        rt.push_back(pos + N);
    return rt;
}

int bfs()
{
    string st, tmp;
    int cnt, pos;
    while (!Q.empty()) {
        st = Q.front().first;
        cnt = Q.front().second;
        pos = st.find("0");
        Q.pop();
        if (mp.count(st)) {
            if (mp[st] == FLG) {
                continue;
            } else if (mp[st] == GOAL) {
                return cnt;
            } else
                printf("ERROR: %d\n", __LINE__);
        }
        mp[st] = FLG;
        vector<int> nb(neighbor(pos));
        for (int i = 0; i < nb.size(); i++) {
            tmp = st;
            tmp[pos] = st[nb[i]]; tmp[nb[i]] = st[pos];
            Q.push(make_pair(tmp, cnt + 1));
        }
    }
    return INT_MIN;
}

int main()
{
    string st, gl = "123456780";
    for (int i = 0; i < 9; i++) {
        int  j;
        cin >> j;
        st += to_string(j);
    }
    mp[gl] = GOAL;
    Q.push(make_pair(st, 0));
    cout << bfs() << endl;
    return 0;
}
```