# define MAXN 362880

struct foot  { int k; char d;};

struct state { char a[N]; };

const char md[4] = {'u', 'l', 'r', 'd'};

const int fact[9] = {1, 1, 2, 6, 24, 120, 720, 720*7, 720*56};

state Q[MAXN+1];

char vis[MAXN];

foot p[MAXN];

int hash(state s)

// 把状态s中的0..8的排列映射为数字 0..(9!-1)

{   

       int i, j, temp, num;   

       num = 0;   

       for (i = 0; i < 9-1; i++)

       {     

            temp = 0; 

            for (j = i + 1; j < 9; j++)

           {

               if (s.a[j] < s.a[i])

               temp++;       

           }

           num += fact[8-i] * temp;

       }

       return num;

}

void print_path(int x, char f)

{

    if (p[x].k == 0) return ;

    if (f)  cout<< md[3-p[x].d];

    print_path(p[x].k, f);

    if (!f) cout<< md[p[x].d];

}

void bfs(state start, state goal)

{

    char t;

    state cur, nst;

    int front, rear, i;

    int space, ct, nt;

    Q[front = 1] = start;

    Q[rear = 2] = goal;

    vis[hash(start)] = 1;  // 1 代表正向

    vis[hash(goal)] = 2;   // 2 代表反向

    while (front <= rear)

    {

        cur = Q[front++];

        ct = hash(cur);

        for (i = 0; cur.a[i] && i < N; ++i) ;

        space=i;

        for (i = 0; i < 4; ++i)

        {

            if(!(i==0 && space<3 || i==1 && space%3==0 || i==2 && space%3==2 ||i==3 && space>5))

            {

                 nst = cur;

                 nst.a[space] = cur.a[space-5+2*(i+1)];

                nst.a[space-5+2*(i+1)] = 0;

                nt = hash(nst);

                if (!vis[nt])

                {

                    Q[++rear] = nst;