#include <iostream>

using namespace std;

int ans[3][3] =
{
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 0}
};
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };

bool match(int f[3][3]) {
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (f[i][j] != ans[i][j])
                return false;
        }
    }
    return true;
}

int dfs(int f[3][3], int x, int y, int v, int d, int l) {
    if (match(f))
        return d;
    if (d > l)
        return -1;
    for (int i = 0, res; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx > 2 || ny < 0 || ny > 2 || (i + 2) % 4 == v)
            continue;
        f[y][x] = f[ny][nx];
        f[ny][nx] = 0;
        if ((res = dfs(f, nx, ny, i, d + 1, l)) > 0)
            return res;
        f[ny][nx] = f[y][x];
        f[y][x] = 0;
    }
    return -1;
}

int main() {
    int f[3][3], x, y;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> f[i][j];
            if (f[i][j] == 0) {
                y = i;
                x = j;
            }
        }
    }

    int res;
    for (int i = 1; i < 50; ++i) {
        if ((res = dfs(f, x, y, -1, 0, i)) >= 0) {
            break;
        }
    }
    cout << res << endl;

    return 0;
}

### Prompt

Develop a solution in CPP 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 <iostream>

using namespace std;

int ans[3][3] =
{
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 0}
};
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };

bool match(int f[3][3]) {
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (f[i][j] != ans[i][j])
                return false;
        }
    }
    return true;
}

int dfs(int f[3][3], int x, int y, int v, int d, int l) {
    if (match(f))
        return d;
    if (d > l)
        return -1;
    for (int i = 0, res; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx > 2 || ny < 0 || ny > 2 || (i + 2) % 4 == v)
            continue;
        f[y][x] = f[ny][nx];
        f[ny][nx] = 0;
        if ((res = dfs(f, nx, ny, i, d + 1, l)) > 0)
            return res;
        f[ny][nx] = f[y][x];
        f[y][x] = 0;
    }
    return -1;
}

int main() {
    int f[3][3], x, y;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> f[i][j];
            if (f[i][j] == 0) {
                y = i;
                x = j;
            }
        }
    }

    int res;
    for (int i = 1; i < 50; ++i) {
        if ((res = dfs(f, x, y, -1, 0, i)) >= 0) {
            break;
        }
    }
    cout << res << endl;

    return 0;
}

```