#include <stdlib.h>
#include <stdio.h>

#define maxhole 10000

typedef enum {none,min1,plus1,maal2,over2} parents;
typedef struct field {
  int distance;
  parents next;
} field;
typedef struct queue {
  int index;
  int dist;
} queue;

int r,runs;
field hole[maxhole+1];
int size;
int fromhole,tohole;


void Init() {
  int i;
  for (i=1;i<=size;i++) {
    hole[i].distance=maxhole*2;
    hole[i].next=none;
  }
}

void Dijkstra() {
  queue q[maxhole+1]; /* Index to hole */
  int qstart,qend;
  field *tmp;

  qstart=0;
  q[0].index=tohole;
  q[0].dist=0;
  qend=1;
  while (qend>qstart) {
    if ((q[qstart].index % 2)==0) {
      tmp=&(hole[q[qstart].index / 2]);
      if (q[qstart].dist<tmp->distance) {
        tmp->distance=q[qstart].dist;
        tmp->next=maal2;
        q[qend].index=q[qstart].index / 2;
        q[qend].dist=q[qstart].dist+1;
        qend++;
      }
    }
    if (q[qstart].index>1) {
      tmp=&(hole[q[qstart].index-1]);
      if (q[qstart].dist<tmp->distance) {
        tmp->distance=q[qstart].dist;
        tmp->next=plus1;
        q[qend].index=q[qstart].index-1;
        q[qend].dist=q[qstart].dist+1;
        qend++;
      }
    }
    if (q[qstart].index<size) {
      tmp=&(hole[q[qstart].index+1]);
      if (q[qstart].dist<tmp->distance) {
        tmp->distance=q[qstart].dist;
        tmp->next=min1;
        q[qend].index=q[qstart].index+1;
        q[qend].dist=q[qstart].dist+1;
        qend++;
      }
    }
    if (q[qstart].index*2<=size) {
      tmp=&(hole[q[qstart].index*2]);
      if (q[qstart].dist<tmp->distance) {
        tmp->distance=q[qstart].dist;
        tmp->next=over2;
        q[qend].index=q[qstart].index*2;
        q[qend].dist=q[qstart].dist+1;
        qend++;
      }
    }
    qstart++;
  }
}


void PrintPath() {
  int current=fromhole;
  printf("%d",current);
  while (current!=tohole) {
    switch (hole[current].next) {
      case none: break; /* eliminates gcc-warning */
      case min1: current-=1; break;
      case plus1: current+=1; break;
      case maal2: current*=2; break;
      case over2: current/=2; break;
    }
    printf(" %d",current);
  }
  printf("\n");
}

int main() {
  scanf("%d",&runs);
  for (r=0;r<runs;r++) {
    scanf("%d",&size);
    Init();
    scanf("%d %d",&fromhole,&tohole);
    hole[tohole].distance=0;
    Dijkstra();
    PrintPath();
  }
  return(0);
}

Generated by Java2Html