#include <bits/stdc++.h>
using namespace std;
int c;
string a;
struct str
{
	string s;//当前状态
	int k;//步数
};
queue<str> q[2];
map<string,int> m[2];
int f(str a)
{
	for(int i=0;i<9;i++)
		if(a.s[i]=='0')
			return i;
}//找'0'在哪里
str U(str a)
{
	swap(a.s[f(a)-3],a.s[f(a)]);
	a.k++;
	return a;
}//空格向上走
str D(str a)
{
	swap(a.s[f(a)],a.s[f(a)+3]);
	a.k++;
	return a;
}//空格向下走
str L(str a)
{
	swap(a.s[f(a)-1],a.s[f(a)]);
	a.k++;
	return a;
}//空格向左走
str R(str a)
{
	swap(a.s[f(a)],a.s[f(a)+1]);
	a.k++;
	return a;
}//空格向右走
int main()
{
	cin>>a;
	q[0].push({a,0});
	q[1].push({"123804765",0});
	m[0][a]=0;
	while(1)
	{
		str t=q[c].front();
		q[c].pop();
		if(c&&m[0].count(t.s))
		{
			cout<<m[0][t.s]+t.k;
			return 0;
		}//队列1和队列2碰上了，输出答案
		if(f(t)>=3&&!m[c].count(U(t).s))
		{
			q[c].push(U(t));
			m[c][U(t).s]=U(t).k;
		}
		if(f(t)<=5&&!m[c].count(D(t).s))
		{
			q[c].push(D(t));
			m[c][D(t).s]=D(t).k;
		}
		if(f(t)%3!=0&&!m[c].count(L(t).s))
		{
			q[c].push(L(t));
			m[c][L(t).s]=L(t).k;
		}
		if(f(t)%3!=2&&!m[c].count(R(t).s))
		{
			q[c].push(R(t));
			m[c][R(t).s]=R(t).k;
		}//尝试四个方向
		c^=1;
	}
	return 0;
}
/*
q0是从起点开始的队列
q1是从终点开始的队列
*/

WA on #1

输入：273645801 标准答案：15 我的答案：17