Untitled

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int ll 
#define set set<int>
#define uset unordered_set<int> 
#define veci vector<int> 
#define vecs vector<string>
#define stack stack<int> 
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end() 
#define FOR(s,n) for(int i = s; i < n; i++)

template<typename T> 
ostream& operator<<(ostream& COUT, vector<T>& v){ for(int i=0 ; i<v.size() ; i++){ COUT<<v[i]<<" "; } COUT << endl; return COUT; }
template<typename T> 
istream& operator>>(istream& CIN, vector<T>& a){ for(int i=0 ; i<a.size() ; i++) CIN>>a[i]; return CIN; }
template<typename T> 
void pws(const T& arg){ cout << arg <<endl;}
template <typename T, typename... Args>
void pws(const T& first, const Args&... args) {cout << first << " ";pws(args...);}

int dir[8][2] = {{0,1},{1,0},{-1,0},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
int MOD = 1e9 + 7;
int n,m,k;

void solve(){

    string s;

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

    string target = "123456789";

    queue<pair<string,int>> q;

    // source is s

    q.push({s,0});

    unordered_map<string,int> vis; // 9! = 3,62,880 possible state of cube possible 

    vis[s] = 1;


    while(!q.empty()){

        auto [str,d] = q.front();q.pop();

        if(str==target) {
            cout<<d<<endl;
            break;
        }

         string temp = str;


         // for horizontal swap possiblity 

        for(int i=0;i<2;i++){

           swap(temp[i],temp[i+1]);

           if(!vis[temp]){
            vis[temp] = 1;
            q.push({temp,d+1});
           }
           
           swap(temp[i],temp[i+1]);

        }

         for(int i=3;i<5;i++){

           swap(temp[i],temp[i+1]);

           if(!vis[temp]){
            vis[temp] = 1;
            q.push({temp,d+1});
           }
           
           swap(temp[i],temp[i+1]);

        }

        for(int i=6;i<9;i++){

           swap(temp[i],temp[i+1]);

           if(!vis[temp]){
            vis[temp] = 1;
            q.push({temp,d+1});
           }
           
           swap(temp[i],temp[i+1]);

        }

        // for veritical swap possiblity 

        for(int i=0;i<6;i++){

            swap(temp[i],temp[i+3]);

          if(!vis[temp]){
            vis[temp] = 1;
            q.push({temp,d+1});
           }
           
           swap(temp[i],temp[i+3]);


        }
    }
       
        
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);   
    int t=1;
    // cin>>t;
    while(t--) solve();
}