#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

int mp[5][5],sx,sy,nx,ny;
int dx[5] = {0, 1, 0, -1, 0}, dy[5] = {0, 0, 1, 0, -1},xb[10]= {1,2,3,1,2,3,1,2,3,0};//判断展开下标
string se;
map<string,bool> vis;
struct point {
	int x;
	int y;
	int step;
	string a;
};
queue<point> q;

string tri_dou() { //三维转二维
	string a;
	for(int i=1; i<=3; i++) {
		for(int j=1; j<=3; j++) {
			a+=char(mp[i][j]+48);
		}
	}
	return a;
}
void dou_tri(string se) { //二维转三维
	for(int i=0; i<9; i++) {
		mp[i/3+1][xb[i]]=se[i]-'0';
	}
}

void bfs() {
	q.push((point) {
		sx,sy,0,se
	});
	vis[se]=1;
	while(!q.empty()) {
		//cout<<"mmsd";
		point nw=q.front();
		q.pop();
		if(nw.a=="123804765") {
			cout<<nw.step;
			return;
		}
		dou_tri(nw.a);
		for(int i=1; i<=4; i++) {
			nx=nw.x+dx[i];
			ny=nw.y+dy[i];
			if(nx>3||nx<1||ny>3||ny<1) continue;
			swap(mp[nw.x][nw.y],mp[nx][ny]);
			string d=tri_dou();
			cout<<d<<' ';
			if(vis.find(d)!=vis.end()) {
				continue;
			}
			q.push((point) {
				nx,ny,nw.step+1,d
			});
			vis[d]=1;
		}
	}
}

int main() {
	cin>>se;
	dou_tri(se);//释放至三维
	for(int i=0; i<9; i++) {
		if(se[i]=='0') {
			sx=i/3+1;
			sy=(i+1)%3;
		}
	}
	bfs();

}