#include <bits/stdc++.h>
using namespace std;
const int movex[] = {1, 0, -1, 0};
const int movey[] = {0, 1, 0, -1};

struct Node{
	int g[4][4];
	Node(int x){
		for (int i=3; i>=1; i--){
			for (int j=3; j>=1; j--){
				g[i][j] = x % 10;
				x /= 10;
			}
		}
	}
	
	int to_int(){
		int res = 0;
		for (int i=1; i<=3; i++){
			for (int j=1; j<=3; j++) res = res * 10 + g[i][j];
		}
		
		return res;
	}
};

using Map = map<int, int>;
using Que = queue<Node>;

void extend(Que q1, Que q2, Map m1, Map m2){
	Node u = q1.front();
	q1.pop();
	cout << u.to_int() << '\n';
	
	int h_1 = u.to_int(), h_2;
	
	int x, y;
	for (int i=1; i<=3; i++){
		for (int j=1; j<=3; j++){
			if (!u.g[i][j]){
				x = i;
				y = j;
				break;
			}
		}
	}
	
	Node v(0);
	int nx, ny;
	for (int i=0; i<4; i++){
		nx = x + movex[i];
		ny = y + movey[i];
		if (nx >= 1 && nx <= 3 && ny >= 1 && ny <= 3){
			v = u;
			swap(v.g[x][y], v.g[nx][ny]);
			
			h_2 = v.to_int();
			if (!m1.count(h_2)) q1.push(v);
			if (m2.count(h_2)){
				cout << m1[h_1] + 1 + m2[h_2];
				exit(0);
			}
		}
	}
}

int st, en = 123804765;

Que q1, q2;
Map m1, m2;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> st;
	
	if (st == en){
		cout << 0;
		return 0;
	}
	
	q1.push(Node(st));
	m1[st] = 0;
	q2.push(Node(en));
	m2[en] = 0;
	
	while (!q1.empty() && !q2.empty()){
		extend(q1, q2, m1, m2);
		extend(q2, q1, m2, m1);
	}
	
	return 0;
}

应该很清晰吧，双向广搜。