#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <windows.h>
#include <time.h>
#include <cstdio>

using namespace std;

class node{
public:
    vector <vector <int> > state;
    int priority;
    int pre;
    int depth;
    int x;
    int y;

    // Constructors
    node(){
        int i;
        this->state.resize(3);
        for(i=0 ; i<3 ; i++)
            state[i].resize(3);
        this->priority = 100;
        this->depth = 0;
        this->pre = -1 ;
        this->x=0;
        this->y=0;

    }

    //Destructors

    //Operators
    void operator=(const node &N){
        this->state = N.state;
        this->pre = N.pre;
        this->priority = N.priority;
        this->depth = N.depth;
        this->x = N.x;
        this->y = N.y;
    }

    //Methods
    void getxy(){
        int i,j;
        for(i = 0 ; i < 3 ; i++)
            for(j = 0 ; j < 3 ; j++){
                if(this->state[i][j] == 0){
                    this->x = i;
                    this->y = j;
                    return;
                }
            }
    }

    bool CanMoveUp();  // (0)
    bool CanMoveDown(); // (1)
    bool CanMoveLeft();  // (2)
    bool CanMoveRight();  // (3)
    bool CanMove(int i);

    node MoveUp();
    node MoveDown();
    node MoveLeft();
    node MoveRight();
    node Move(int i);
};

bool node::CanMoveUp(){
    if(this->x == 0 || this->pre == 0)
        return false;
    return true;
}

bool node::CanMoveDown(){
    if(this->x == 2 || this->pre == 1)
        return false;
    return true;
}

bool node::CanMoveLeft(){
    if(this->y == 0 || this->pre == 2)
        return false;
    return true;
}

bool node::CanMoveRight(){
    if(this->y == 2 || this->pre == 3)
        return false;
    return true;
}

bool node::CanMove(int i){
    if(i==0) return this->CanMoveUp();
    if(i==1) return this->CanMoveDown();
    if(i==2) return this->CanMoveLeft();
    if(i==3) return this->CanMoveRight();
}

node node::MoveUp(){
    node result;
    result.state = this->state;
    result.depth = this->depth + 1;
    result.pre = 1;
    result.x = this->x;
    result.y = this->y;
    swap(result.state[x][y],result.state[x-1][y]);
    result.x = this->x - 1;
    //Priority have to been updated after move
    return result;
}

node node::MoveDown(){
    node result;
    result.state = this->state;
    result.depth = this->depth + 1;
    result.pre = 0;
    result.x = this->x;
    result.y = this->y;
    swap(result.state[x][y],result.state[x+1][y]);
    result.x = this->x + 1;
    //Priority have to been updated after move
    return result;
}

node node::MoveLeft(){
    node result;
    result.state = this->state;
    result.depth = this->depth + 1;
    result.pre = 3;
    result.x = this->x;
    result.y = this->y;
    swap(result.state[x][y],result.state[x][y-1]);
    result.y = y - 1;
    //Priority have to been updated after move
    return result;
}

node node::MoveRight(){
    node result;
    result.state = this->state;
    result.depth = this->depth + 1;
    result.pre = 2;
    result.x = this->x;
    result.y = this->y;
    swap(result.state[x][y],result.state[x][y+1]);
    result.y = y + 1;
    //Priority have to been updated after move
    return result;
}

node node::Move(int i){
    if(i==0) return this->MoveUp();
    if(i==1) return this->MoveDown();
    if(i==2) return this->MoveLeft();
    if(i==3) return this->MoveRight();
}
//end methods

//used to compare 2 Node's priority to pussh them into priority_queue.
struct cmp{
    bool operator()(node A, node B){
        if(A.priority == B.priority) return (A.depth > B.depth);
        return A.priority > B.priority;
    }
};


int* get_pos(int a, node des){
    int i,j;
    int *result = new int[2];
    for(i = 0 ; i < 3 ; i++){
        for(j = 0 ; j < 3 ; j++){
            if(des.state[i][j] == a)
            {
                result[0] = i;
                result[1] = j;
                return result;
            }
        }
    }
}

//function to get priority (heuristic search)
int get_priority(node current, node des){
    int i,j,result = 0;
    int *pos = new int[2];
    for(i = 0 ; i < 3 ; i++){
        for(j = 0 ; j < 3; j++){
            if(current.state[i][j] != 0){
                pos = get_pos(current.state[i][j],des);
                result += (pos[0]-i)*(pos[0]-i) + (pos[1]-j)*(pos[1]-j);
            }
        }
    }
    return result;
}



int Find(node x, vector<node> seen){
    int i;
    for(i=0;i<seen.size();i++){
        if(x.state == seen[i].state) return seen[i].pre;
    }
    return -1;
}



void Cout(vector<vector <int> > a){
    int i,j;
    cout<<endl;
    for(i=0 ; i<3; i++){
        for(j=0 ; j<3; j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
}


bool CanFind(node x, priority_queue <node,vector<node>,cmp> &q ){
    priority_queue <node,vector<node>,cmp> new_q;
    bool result=false;
    while(!q.empty()){
        node current = q.top();
        q.pop();
        if(x.state == current.state ){
            if(x.depth < current.depth)
                new_q.push(x);
            else new_q.push(current);
            result = true;
        }
        else new_q.push(current);
    }
    q = new_q;
    return result;
}

bool CanFind_Seen(node x, vector<node> &seen,priority_queue <node,vector<node>,cmp> &pq ){
    int i;
    for(i = 0; i<seen.size() ;i++){
        if(x.state == seen[i].state){
            if(x.depth < seen[i].depth){

                pq.push(x);
                seen.erase(seen.begin()+i);
            }//endif
            return true;
        }//endif
    }//endfor
    return false;
}

bool CanFind_Seenv2(node x, vector<node> seen ){
    int i;
    for(i = 0; i<seen.size() ;i++){
        if(x.state == seen[i].state){
            return true;
        }//endif
    }//endfor
    return false;
}

int get_total(node current, node des){
    int i,j,result = 0;
    for(i = 0 ; i < 3 ; i++){
        for(j = 0 ; j < 3 ; j++){
            if(current.state[i][j] != 0 && current.state[i][j]!= des.state[i][j])
                result++;
        }
    }
    return result;
}

void go(node start, node des){
    priority_queue <node,vector<node>,cmp> pq;
    vector<node> seen;
    // store nodes which have been seen before.
    // Chứa các node đã xem qua
    int i,j,loop=0;
    bool inSeen,inPQ;
    node neightbor,temp,current;
    start.getxy();
    start.priority = get_priority(start,des);
    // get priority of start node.
    // tính độ ưu tiên cho node start.
    pq.push(start);
    //thêm start vào pq
    while(!pq.empty()){
        current = pq.top(); // xét node current có độ ưu tiên thấp nhất trong pq.
        pq.pop(); //loại bỏ nó khỏi pq.
        if (!CanFind_Seenv2(current,seen)){
        loop++;
        seen.push_back(current); //đánh dấu nó đã xem qua rồi.
        //Nếu current là đích dừng lại và in kết quả
        if (current.state == des.state) {
                temp = current; // biến này dùng để in kết quả
                break;
        }
        //Find the neghtbor nodes:
        //Tìm các node con của node current
        for(i=0;i<4;i++){
            if(current.CanMove(i)){
                // Với mỗi node con neighbor của current
                neightbor = current.Move(i);
                //Tình priority cho neighbor
                neightbor.priority = get_priority(neightbor,des) /*+get_total(neightbor,des)*/+ neightbor.depth;
                //cout<<"depth: "<<neightbor.depth<<"     heu:"<<h<<"    ";
                //Nếu chưa thấy trước đó, thêm nó vào pq
                //inSeen = CanFind_Seen(neightbor,seen,pq);
                //inPQ = CanFind(neightbor,pq);
                //if(!inSeen && !inPQ){
                pq.push(neightbor);
                //}
            }//endif
        }//endfor
        }
    }//endwhile
    //print the result

    cout<<"steps:"<<temp.depth<<endl;
    vector<node> result;
    result.push_back(temp);
    temp = temp.Move(temp.pre);
    while(1){
        //Cout(temp.state);
        result.push_back(temp);
        int next = Find(temp,seen);
        if (next == -1) break;
        temp = temp.Move(next);
    }
    for(i=result.size()-1 ; i>=0 ; i--){
        Cout(result[i].state);
        //Sleep(1000);
    }
    cout<<"Loop:"<<loop<<endl;
    cout<<"steps:"<<result.size()-1<<endl;

}

int main()
{
    clock_t t;

    for(int t=0;t<100;t++){

    node start, des;
    int i,j;
    //start.priority = get_priority(start,des) + start.depth  ;
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
            cin>>start.state[i][j];
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
            cin>>des.state[i][j];
     t = clock();
    //cout<<get_priority(start,des);
    go(start,des);
    cout<<"done.";
    t = clock() - t;
    cout<<"Time: "<<((float)t)/CLOCKS_PER_SEC<<" s";
    cin>>i;
    }
}