Link to this code: https://cses.fi/paste/5b823493d891d75d12d603/
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...) 6;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

vector<string> v;
vector<pair<int, int>> swaps;
unordered_map<string, int> mp;

vector<int> bfs(int s) {
    vector<int> dist(v.size(), -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (dist[u] == 8)
            continue;
        string cur = v[u];
        for (auto [i, j] : swaps) {
            swap(cur[i], cur[j]);
            int x = mp[cur];
            if (dist[x] == -1) {
                dist[x] = dist[u] + 1;
                q.push(x);
            }
            swap(cur[i], cur[j]);
        }
    }
    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string a;
    for (int i=0; i<9; i++) {
        int x;
        cin >> x;
        a += (char) (x + '0');
    }

    string s = "123456789";
    do {
        mp[s] = v.size();
        v.push_back(s);
    } while (next_permutation(s.begin(), s.end()));
    int goal = mp[a];

    for (int i=0; i<3; i++)
            for (int j=0; j<3; j++) {
                if (i < 2)
                    swaps.emplace_back(3 * i + j, 3 * (i + 1) + j);
                if (j < 2)
                    swaps.emplace_back(3 * i + j, 3 * i + j + 1);
            }

    vector<int> dist1 = bfs(0), dist2 = bfs(goal);
    int ret = INT_MAX;
    for (int i=0; i<(int)dist1.size(); i++)
        if (dist1[i] != -1 && dist2[i] != -1)
            ret = min(ret, dist1[i] + dist2[i]);
    cout << ret << "\n";

    return 0;
}