#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;
const ll MAX = 3;
ll LIMIT = 35;

ll A[MAX][MAX];
ll x[4] = {0, 1, 0, -1};
ll y[4] = {1, 0, -1, 0};

ll dfs(pll s, ll match, pll prev = pll(-1, -1), ll cnt = 0) {
    if (match == MAX * MAX - 1) {
        return cnt;
    }
    if (LIMIT <= cnt)
        return INF;
    if (LIMIT < cnt + (MAX - s.first - 1) + (MAX - s.second - 1))
        return INF;

    ll ret = INF;
    REP(i, 4) {
        ll nx = x[i] + s.first, ny = y[i] + s.second;
        if (nx < 0 || ny < 0 || nx >= MAX || ny >= MAX)
            continue;
        if (prev.first == nx && prev.second == ny)
            continue;
        ll m = match;
        if (A[nx][ny] == nx * MAX + ny + 1)
            m--;
        else if (A[nx][ny] == s.first * MAX + s.second + 1)
            m++;
        swap(A[s.first][s.second], A[nx][ny]);
        ret = std::min(ret, dfs(pll(nx, ny), m, s, cnt + 1));
        swap(A[s.first][s.second], A[nx][ny]);
    }
    LIMIT = std::min(LIMIT, ret);
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    pll s;
    REP(i, MAX) {
        REP(j, MAX) {
            cin >> A[i][j];
            if (A[i][j] == 0)
                s = pll(i, j);
        }
    }

    ll match = 0;
    REP(i, MAX) {
        REP(j, MAX) {
            ll num = i * MAX + j + 1;
            if (A[i][j] == num)
                match++;
        }
    }

    cout << dfs(s, match) << endl;
    return 0;
}

### Prompt

Generate 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 int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;
const ll MAX = 3;
ll LIMIT = 35;

ll A[MAX][MAX];
ll x[4] = {0, 1, 0, -1};
ll y[4] = {1, 0, -1, 0};

ll dfs(pll s, ll match, pll prev = pll(-1, -1), ll cnt = 0) {
    if (match == MAX * MAX - 1) {
        return cnt;
    }
    if (LIMIT <= cnt)
        return INF;
    if (LIMIT < cnt + (MAX - s.first - 1) + (MAX - s.second - 1))
        return INF;

    ll ret = INF;
    REP(i, 4) {
        ll nx = x[i] + s.first, ny = y[i] + s.second;
        if (nx < 0 || ny < 0 || nx >= MAX || ny >= MAX)
            continue;
        if (prev.first == nx && prev.second == ny)
            continue;
        ll m = match;
        if (A[nx][ny] == nx * MAX + ny + 1)
            m--;
        else if (A[nx][ny] == s.first * MAX + s.second + 1)
            m++;
        swap(A[s.first][s.second], A[nx][ny]);
        ret = std::min(ret, dfs(pll(nx, ny), m, s, cnt + 1));
        swap(A[s.first][s.second], A[nx][ny]);
    }
    LIMIT = std::min(LIMIT, ret);
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    pll s;
    REP(i, MAX) {
        REP(j, MAX) {
            cin >> A[i][j];
            if (A[i][j] == 0)
                s = pll(i, j);
        }
    }

    ll match = 0;
    REP(i, MAX) {
        REP(j, MAX) {
            ll num = i * MAX + j + 1;
            if (A[i][j] == num)
                match++;
        }
    }

    cout << dfs(s, match) << endl;
    return 0;
}

```