MLE

#include<bits/stdc++.h>
using namespace std;

struct qwq{
	long long step;
	bool shang,xia,zuo,you;
	int xy;
	string s;
}hand,al;

int a,b;
queue<qwq> q;
string js; 

void f(){
	cin>>hand.s;
    js="123804765";
	hand.xy=hand.s.find('0');
	q.push(hand);
	while(!q.empty()){
		al=q.front();
		q.pop();
		if(al.s==js){
			cout<<al.step;
			return ;
		}
		a=al.xy/3;b=al.xy%3;
		qwq ar;
		ar.step=al.step+1;
		if(a!=0&&!al.shang){//上
			ar.xia=1;
			ar.s=al.s;
			ar.xy=al.xy-3;
			swap(ar.s[al.xy],ar.s[ar.xy]);
			q.push(ar);
			ar.xia=0;
		}
		if(a!=2&&!al.xia){//下 
			ar.shang=1;
			ar.s=al.s;
			ar.xy=al.xy+3;
			swap(ar.s[al.xy],ar.s[ar.xy]);
			q.push(ar);
			ar.shang=0;
		}
		if(b!=0&&!al.zuo){//左
			ar.you=1;
			ar.s=al.s;
			ar.xy=al.xy-1;
			swap(ar.s[al.xy],ar.s[ar.xy]);
			q.push(ar);
			ar.you=0;
		}
		if(b!=2&&!al.you){//右 
			ar.zuo=1;
			ar.s=al.s;
			ar.xy=al.xy+1;
			swap(ar.s[al.xy],ar.s[ar.xy]);
			q.push(ar);
			ar.zuo=0;
		}
	}
}

int main(){
	f();
	return 0;
}