#include <iostream>
#include <queue>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cctype>

using namespace std;

typedef long long Board;

const int N = 9;
const Board GOAL = 0x087654321;

const int PATTERN = 362880;
const int FORWARD  = 1;
const int BACKWARD = 2;
int frontier[PATTERN];

struct State {
    Board board;
    int count;
};

queue<State> q;

// I made this function based on one by Haruhiko Okumura(Algorithm 
// Dictionary, p116) and one by M.Hiroi(Puzzle DE Programming).
inline int change_number(long long board) {
    static int fact_table[N] = {
         40320, 5040, 720, 120, 24, 6, 2, 1, 0      // on N = 8
    };
    int value = 0;
    for (int j = 0; j < N - 1; ++j) {
        int J = static_cast<int>((board >> (j*4) & 0xF));
        value += fact_table[j] * J;
        for (int k = j + 1; k < N; ++k) {
            int K = static_cast<int>((board >> k*4) & 0xF);
            if (J < K) {
                board &= ~(0xFLL << k*4);
                board |= (static_cast<long long>(K - 1) << k*4);
            }
        }
    }
//    printf("[change_number] value = %d\n", value);
    return value;
}

inline void swap(int numpos, int spacepos, Board& board) {
    long long num = (board >> (numpos*4)) & 0xF;
    board |= num << (spacepos*4);
    board &= ~(0xFLL << (numpos*4));
}

inline int swap_and_check(int numpos, int spacepos, State s) {
    int prev = change_number(s.board);
    int direction = frontier[prev];
//    printf("[swap&check] direction = %d\n", direction);
    swap(numpos, spacepos, s.board);
//    if (s.board == GOAL) {
//        return ++s.count;
//    }
    int pos = change_number(s.board);
    if (!frontier[pos]) {
        ++s.count;
        q.push(s);
        frontier[pos] = direction;
        return -1;
    }
    else if (frontier[pos] != direction) {
        ++s.count;
//        printf("[swap&check] s.count = %d\n", s.count);
//        return s.count * 2 + direction - 1;
//        return s.count * 2;
        return s.count * 2 - (frontier[pos] - 1);
    }
    return -1;
}

void print(Board b) {
    for (int i = 0; i < N; ++i) {
        printf("%2lld", (b >> (i*4) & 0xF));
    }
    printf("\n");
}

// OK
int main(void) {

    Board board = 0;
    for (int i = 0, num; i < N; ++i) {
        scanf("%d", &num);
        board |= static_cast<long long>(num) << (i*4);
    }
//    print(GOAL);
//    print(board);

    int count = 0;
    if (board == GOAL) {
        goto END;
    }

    frontier[change_number(board)] = FORWARD;
    frontier[change_number(GOAL)] = BACKWARD;

    q.push({ board, 0 });
    q.push({ GOAL, 0 });
    while (!q.empty()) {
        State s = q.front();
        q.pop();

        int pos = -1;
        while (++pos < N) {
            if (((s.board >> (pos*4)) & 0xF) == 0) {
                break;
            }
        }

        if (pos < 6) {
            if ((count = swap_and_check(pos + 3, pos, s)) > 0) {
                break;
            }
        }
        if (pos > 2) {
            if ((count = swap_and_check(pos - 3, pos, s)) > 0) {
                break;
            }
        }
        if (pos % 3 < 2) {
            if ((count = swap_and_check(pos + 1, pos, s)) > 0) {
                break;
            }
        }
        if (pos % 3 > 0) {
            if ((count = swap_and_check(pos - 1, pos, s)) > 0) {
                break;
            }
        }
    }

END:
    printf("%d\n", count);

    return 0;
}

Measured memory_bytes: 2716