#include <bits/stdc++.h>
using namespace std;
string sta;
string ans = "123804765";
inline int where(string x) {
	for (int i = 0; i < 9 ; ++i) {
		if (x[i] == '0')return i;
	}
}
inline string solve(char c, string y) {
	switch (c) {
		case 'r' :
			swap(y[where(y)], y[where(y) + 1]);
		case 'l' :
			swap(y[where(y)], y[where(y) - 1]);
		case 'u' :
			swap(y[where(y)], y[where(y) + 3]);
		case 'd' :
			swap(y[where(y)], y[where(y) - 3]);
	}
	return y;
}
inline vector<string> dfs(string x) {
	vector<string> v;
	string y = x;
	if ((where(x) % 3 != 2)) {
		swap(y[where(y)], y[where(y) + 1]);
		v.push_back(y);
	}
	y = x;
	if ((where(x) % 3)) {
		swap(y[where(y)], y[where(y) - 1]);
		v.push_back(y);
	}
	y = x;
	if ((where(x) / 3)) {
		swap(y[where(y)], y[where(y) + 3]);
		v.push_back(y);
	}
	y = x;
	if ((where(x) >= 6)) {
		swap(y[where(y)], y[where(y) - 3]);
		v.push_back(y);
	}

	return v;
}
set<string>m1, m2;
#define f(a,b) (a.find(b)!=a.end())
inline int bfs() {
	queue<string> q1, q2;
	int cnt = 0;
	q1.push(sta);
	q2.push(ans);
	while (q1.front() != q2.front()) {
		string t1 = q1.front();
		string t2 = q2.front();
		q1.pop();
		q2.pop();
		if (f(m1, t2) || f(m2, t1))break;
		if (!f(m1, t1)) {
			m1.insert(t1);
			vector<string> tv = dfs(t1);
			for (string s : tv) {
				q1.push(s);
			}
		}
		if (!f(m2, t2)) {
			m1.insert(t2);
			vector<string> tv = dfs(t2);
			for (string s : tv) {
				q2.push(s);
			}
		}
		++cnt;
	}
	return cnt;
}
int main() {
	string x;
	cin >> x;
	sta = x;
	cout << bfs();
	return 0;
}

双向广搜，#1~#30 全$\color{red}WA$,#31$\color{green}AC$

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

string ans = "123804765";
inline int f(string x) {
	int ret = 0;
	if (x == ans)return 0x3f3f3f3f;
	for (int i = 0; i < 9 ; ++i) if (x[i] == ans[i])++ret;
	return ret;
}
inline int where(string x) {
	for (int i = 0; i < 9 ; ++i) {
		if (x[i] == '0')return i;
	}
}
inline string solve(char c, string y) {
	switch (c) {
		case 'r' :
			swap(y[where(y)], y[where(y) + 1]);
		case 'l' :
			swap(y[where(y)], y[where(y) - 1]);
		case 'u' :
			swap(y[where(y)], y[where(y) + 3]);
		case 'd' :
			swap(y[where(y)], y[where(y) - 3]);
	}
	return y;
}
inline int dfs(string x) {
	if (x == ans)return 0;
	int cnt = 0x3f3f3f3f;
	vector<pair<int, char > > v;
	int t = 0;
	string y = x;
	if (t = (where(x) % 3 != 2)) {
		swap(y[where(y)], y[where(y) + 1]);
		v.push_back(make_pair(t, 'r'));
	}
	y = x;
	if (t = (where(x) % 3)) {
		swap(y[where(y)], y[where(y) - 1]);
		v.push_back(make_pair(t, 'l'));
	}
	y = x;
	if (t = (where(x) / 3)) {
		swap(y[where(y)], y[where(y) + 3]);
		v.push_back(make_pair(t, 'u'));
	}
	y = x;
	if (t = (where(x) >= 6)) {
		swap(y[where(y)], y[where(y) - 3]);
		v.push_back(make_pair(t, 'd'));
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); ++i) {
		cnt = min(cnt, dfs(solve(v[i].second, x)) + 1);
	}
	return cnt;
}
int main() {
	string x;
	cin >> x;
	cout << dfs(x);
	return 0;
}

IDA*,#1~#30$\color{black}MLE$#31 $\color{green}AC$