#include<string>
#include<queue>
#include<map>
using namespace std;
struct node
{
	string a;
	long long step;
};
string s,t = "123804765";
long long d[] = {0,1,3,-1,-3};
map <string,bool> vis;
queue <node> q;

int main()
{
	cin>>s;
	vis[s] = 0;
	q.push((node){s,0});
	while(!q.empty())
	{
		node w = q.front();
		q.pop();
		cout<<"("<<w.a<<' '<<w.step<<") ";
		if(w.a == t)
		{
			cout<<w.step;
			return 0;
		}
		for(int i=1;i<=4;++i)
		{
			node t = (node){w.a , w.step + 1};
			int x = t.a.find("0");
			int y = x + d[i];
			if(0 <= y && y <= 8)
			{
				swap(t.a[x] , t.a[y]);
				if(!vis[t.a])
				{
					q.push(t);
					vis[t.a] = 1;
				}
			}
		}
		cout<<'\n';
	}
	return 0;
}