#include <iostream>
using namespace std;
static const int LINE = 3;
static const int N = 9;

int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
int ans[LINE][LINE];
int in[LINE][LINE];

int check(){

    for(int i=0; i<LINE; i++){
        for(int j=0; j<LINE; j++){
            if(in[i][j] != ans[i][j])
                return false;
        }
    }

    return true;
}

int dfs(int x, int y, int d,int u,int k){
    if(check()) return d;
    if(d > k) return -1;
    for(int i=0; i<4; i++){
        int vx,vy,val;
        vx = x+dx[i];
        vy = y+dy[i];

        if(vx > 2 || vx < 0 || vy > 2 || vy < 0 || (i + 2) % 4 == u ){
            continue;
        }
        in[y][x] = in[vy][vx];
        in[vy][vx] = 0;
        val  = dfs(vx,vy,d+1,i,k);
        if(val > 0) return val;
        in[vy][vx] = in[y][x];
        in[y][x] = 0;
    }
    return -1;
}


int main(){
    int x,y,sol,cnt=0;

    for(int i=0; i<LINE; i++){
        for(int j=0; j<LINE; j++){
            ans[i][j] = ++cnt;
            if(i == LINE-1 && j == LINE -1) ans[i][j] = 0;
        }
    }

    for(int i=0; i<LINE; i++){
        for(int j=0; j<LINE; j++){
            cin>>in[i][j];
            if(in[i][j] == 0){
                y = i;
                x = j;
            }
        }
    }

    cnt = 1;

    while(1){
        sol = dfs(x,y,0,-1,cnt);
        if(sol >= 0) break;
        cnt++;
    }

    /*for(int i=0; i<LINE; i++){
        for(int j=0; j<LINE; j++){
            cout<<in[i][j];
        }
        cout<<endl;
    }*/ //出力確認


    cout<<sol<<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;
static const int LINE = 3;
static const int N = 9;

int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
int ans[LINE][LINE];
int in[LINE][LINE];

int check(){

    for(int i=0; i<LINE; i++){
        for(int j=0; j<LINE; j++){
            if(in[i][j] != ans[i][j])
                return false;
        }
    }

    return true;
}

int dfs(int x, int y, int d,int u,int k){
    if(check()) return d;
    if(d > k) return -1;
    for(int i=0; i<4; i++){
        int vx,vy,val;
        vx = x+dx[i];
        vy = y+dy[i];

        if(vx > 2 || vx < 0 || vy > 2 || vy < 0 || (i + 2) % 4 == u ){
            continue;
        }
        in[y][x] = in[vy][vx];
        in[vy][vx] = 0;
        val  = dfs(vx,vy,d+1,i,k);
        if(val > 0) return val;
        in[vy][vx] = in[y][x];
        in[y][x] = 0;
    }
    return -1;
}


int main(){
    int x,y,sol,cnt=0;

    for(int i=0; i<LINE; i++){
        for(int j=0; j<LINE; j++){
            ans[i][j] = ++cnt;
            if(i == LINE-1 && j == LINE -1) ans[i][j] = 0;
        }
    }

    for(int i=0; i<LINE; i++){
        for(int j=0; j<LINE; j++){
            cin>>in[i][j];
            if(in[i][j] == 0){
                y = i;
                x = j;
            }
        }
    }

    cnt = 1;

    while(1){
        sol = dfs(x,y,0,-1,cnt);
        if(sol >= 0) break;
        cnt++;
    }

    /*for(int i=0; i<LINE; i++){
        for(int j=0; j<LINE; j++){
            cout<<in[i][j];
        }
        cout<<endl;
    }*/ //出力確認


    cout<<sol<<endl;

    return 0;
}




```