#define rand lrand48
#define srand srand48
/* POTM ENTRY: Lord_Bitish 0x10V
 *
 * This Sorry Piece of Programming Was Done By: Chad Hurwitz 
 *
 * compile with cc; if Test gets 204, then use gcc;
 * if cant link lrand48, comment above #defines
 */
#define SEED 0

#define GRID 100
#define CUST 100
#define ITERS ITERS_VAL(CUST+1)
#define BESTA BESTA_VAL(CUST+1)
#define BESTA_VAL(_v) (1+((_v)*2)/3)
#define ITERS_VAL(_v) ((_v)*2)
#define MOVE_LIMIT ((CUST+1)*10)
#ifdef STAYUNDER100
#define TMARK 2
#else
#define TMARK 1
#endif

#include 
#include 
#ifndef max
#define max(_a,_b) (((_a)>(_b))?_a:(_b))
#endif

#define MAXP 100
#define GOBX 0x01
#define GOBY 0x02
#define GOBXY 0x04
#define GOBZ 0x08
#define GOBXZ 0x10
#define GOBYZ 0x20

#define NO_ID -1
#define MAX_DEGREE 101
#define MAX_COST 9999
#define cost_t int
#define MIN_SUM -999999
#define MAX_SUM 999999
#define SUM_GRANU 1
#define sum_t long
#define city_id_t int
#define val(_a,_b) (matptr[_a][_b])
#define valarray(_a) (matptr[_a])

#if CUST > GRID*2
error
#endif
#define GSIZE (3*GRID/2)
#define GRIDSIZE max(GSIZE,CUST)
#define BEVEL 4
int moves_bak[MOVE_LIMIT*2];
city_id_t xtracopy[CUST+1], degree, tourcopy[CUST+1+1];
cost_t matrix[GRIDSIZE+BEVEL][GRIDSIZE+BEVEL], *matrixptr[GRIDSIZE+BEVEL];
cost_t **matptr;
int moves_c[MOVE_LIMIT*2], move_ptr[CUST+1+1], moves, movep, total_moves;
int xloc[CUST+1+1], yloc[CUST+1+1];
int move_again[CUST+1], checked_custs, checked_cust[CUST*2];

static void plop(x, y, z, gob)
   city_id_t *x, *y, *z; int gob;
{
   city_id_t i;
   if (gob&GOBX) {
      for (i=0; i < (y-x)/2; i++)
	 xtracopy[i] = x[i+1];
      for (i=0; i < (y-x)/2; i++)
	 x[i+1] = x[(int)(y-x)-i];
      for (i=0; i < (y-x)/2; i++)
	 x[(int)(y-x)-i] = xtracopy[i];
   }
   if (gob&GOBY) {
      for (i=0; i < (z-y)/2; i++)
	 xtracopy[i] = y[i+1];
      for (i=0; i < (z-y)/2; i++)
	 y[i+1] = y[(int)(z-y)-i];
      for (i=0; i < (z-y)/2; i++)
	 y[(int)(z-y)-i] = xtracopy[i];
   }
   if (gob&GOBXY) {
      for (i=0; i < (y-x); i++)
	 xtracopy[i] = x[i+1];
      for (i=0; i < (z-y); i++)
	 x[i+1] = y[i+1];
      for (i=0; i < (y-x); i++)
	 z[i+1-(city_id_t)(y-x)] = xtracopy[i];
   }
   tourcopy[degree] = tourcopy[0];
}
#define PLOP(a,b,c,e,f) plop(a,b,c,e)

#define SUM_GREATER(a,b) ((a)>(b))

static city_id_t find_j_and_swap(k, i)
   city_id_t *k, i;
{
   register city_id_t j, last_j = *k, lj, *forwardk = xtracopy+last_j;

   j = *forwardk;
   *forwardk = i;
   tourcopy[i] = last_j;
   for (forwardk = xtracopy+j; j != i; forwardk = xtracopy+j) {
      lj = last_j;
      tourcopy[lj] = last_j = j;
      j = *forwardk;
      *forwardk = lj;
   }
   tourcopy[last_j] = (city_id_t)(k-xtracopy);
   *k = last_j;
   return *k = last_j;
}

static int nudge()
{
   static city_id_t besttour[CUST+1], added[CUST+1], removed[CUST+1];
   register city_id_t *kptr, *end, *tadd, *trem, *bptr;
   register city_id_t ii=NO_ID, i=NO_ID, k, removed_k, downk;
   city_id_t startl, endl, j, last_l;
   sum_t GS, gp, bestGS=MIN_SUM;
   cost_t *cost, mincost, tmpcost;
   int p, bettered = 0;

   for (kptr = tourcopy, end = kptr+degree; kptr < end; kptr++)
      xtracopy[*kptr] = kptr[1];
   memcpy(besttour, xtracopy, sizeof(city_id_t)*degree);
   endl = degree-1;
   for (startl = 0; startl != endl; startl = (startl+1)%degree) {
      for (end=(kptr=xtracopy)+degree, tadd=added, trem=removed; kptr < end; ) {
	 tourcopy[*kptr] = (city_id_t)(kptr-xtracopy); kptr++;
	 *tadd++ = *trem++ = NO_ID;
      }
      kptr = xtracopy + startl;
      removed[*kptr] = last_l = startl;
      for (p = 0, gp = 0, bestGS = -SUM_GRANU*2; gp > bestGS; p++) {
	 k = *kptr;
	 mincost = MAX_COST;
	 removed_k = removed[k];
	 tadd = added;
	 trem = removed;
	 cost = valarray(k);
	 bptr = tourcopy;
	 downk = xtracopy[k];
	 for (ii = 0; ii < degree; ii++, tadd++, trem++, cost++, bptr++) {
	    tmpcost = *cost - val(ii,*bptr);
	    if (mincost > tmpcost) {
	       if (ii != k && ii != downk && ii != removed_k && k != *trem) {
		  if (*tadd == MAX_DEGREE)
		     ;
		  else if (*tadd == NO_ID || *tadd != *bptr) {
		     mincost = tmpcost;
		     i = ii;
		  }
	       }
	    }
	 }
	 if (mincost == MAX_COST || i == startl)
	    break;
	 gp += val(last_l, k) - val(k, i);
	 last_l = i;
	 downk = tourcopy[i];
	 j = find_j_and_swap(kptr, i);
	 if (removed[i] == NO_ID)
	    removed[i] = j;
	 else
	    removed[j] = i;
	 if (added[i] == NO_ID)
	    added[i] = k;
	 else
	    added[i] = MAX_DEGREE;
	 if (added[k] == NO_ID)
	    added[k] = i;
	 else
	    added[k] = MAX_DEGREE;
	
	 GS = gp + val(i, j) - val(j, startl);
	 if (bestGS < GS && GS > 0) {
	    bestGS = GS;
	    memcpy(besttour, xtracopy, sizeof(city_id_t)*degree);
	 }
	 if (p >= MAXP && (gp <= 0 || tourcopy[j] || gp <= bestGS))
	    break;
      }
      if (bestGS > 0) {
	 endl = startl;
	 bettered = 1;
      }
      memcpy(xtracopy, besttour, sizeof(city_id_t)*degree);
   }
   for (i=j=0; i ydiff) {
      diff = xdiff;
      xdiff = ydiff;
      ydiff = diff;
   }
   odd = (xdiff + ydiff) % 2;
   if (ydiff < SMALL_ARRAY_SIZE) {
      if (x1 == y1 && x2 == y2 && xdiff == 1 && (x1 == 0 || x2 == 0))
	 dist = 4;
      else
	 dist = small_dist[xdiff*SMALL_ARRAY_SIZE + ydiff];
   }
   else if (!(diff = ydiff - 2*xdiff))
      dist = xdiff;
   else if (diff > 0.) {
      int seg1 = (ydiff - 1) / 2 + 1, seg2;
      if (seg1 % 2)
	 seg2 = seg1 + 1;
      else {
	 seg2 = seg1;
	 seg1 = seg2 + 1;
      }
      if (odd)
	 dist = seg1;
      else
	 dist = seg2;
   }
   else {
      if (odd)
	 dist = ((xdiff + (ydiff - xdiff) / 2 + 1) / 3) * 2 + 1;
      else
	 dist = ((xdiff + (ydiff - xdiff) / 2 - 1) / 3) * 2 + 2;
   }
   return dist;
}

static int distance_where(x1, y1, x2, y2)
   int x1, y1, x2, y2;
{
   int xdiff, ydiff, diff, ret, rot, flip;
   static int small_ret[] = { 0xff, 0xdb, 0x42, 0xa5, 0x81, 0xc3, 0xc3,
   0xe7, 0x81, 0xc3, 0xc3, 0xdb, 0x84, 0x01, 0x82, 0x43, 0xe7, 0x81, 0xc3,
   0xc3, 0xe7, 0x81, 0x42, 0x01, 0xff, 0xc7, 0x01, 0x83, 0xc3, 0xe7, 0x81,
   0xc3, 0xc3, 0xa5, 0x82, 0xc7, 0x03, 0x82, 0xc7, 0x01, 0x83, 0xc3, 0xe7,
   0x81, 0x81, 0x43, 0x01, 0x82, 0xcf, 0x03, 0x83, 0xc7, 0x01, 0x83, 0xc3,
   0xc3, 0xe7, 0x83, 0xc7, 0x03, 0x87, 0xcf, 0x03, 0x83, 0xc7, 0x01,
   0xc3, 0x81, 0xc3, 0x01, 0x83, 0xcf, 0x03, 0x87, 0xcf, 0x03, 0x83,
   0xe7, 0xc3, 0xe7, 0x83, 0xc7, 0x03, 0x87, 0xcf, 0x03, 0x87, 0xcf,
   0x81, 0xc3, 0x81, 0xc3, 0x01, 0x83, 0xcf, 0x03, 0x87, 0xcf, 0x03,
   0xc3, 0xe7, 0xc3, 0xe7, 0x83, 0xc7, 0x03, 0x87, 0xcf, 0x03, 0x87,
   0xc3, 0x81, 0xc3, 0x81, 0xc3, 0x01, 0x83, 0xcf, 0x03, 0x87, 0xcf };

   xdiff = x2 - x1;
   ydiff = y2 - y1;
   if (xdiff < 0) {
      xdiff *= -1;
      rot = 2;
   }
   else
      rot = 0;
   if (ydiff < 0) {
      ydiff *= -1;
      if (!rot)
	 rot++;
   }
   else
      if (rot)
	 rot++;
   if (xdiff > ydiff) {
      diff = xdiff;
      xdiff = ydiff;
      ydiff = diff;
      flip = (!(rot % 2)) ? 1 : 0;
   }
   else {
      flip = (rot % 2) ? 1 : 0;
   }
   if (ydiff < SMALL_ARRAY_SIZE) {
      if ((x1 == 0 && y1 == 0) || (x2 == 0 && y2 == 0)) {
	 if (xdiff == 1 && ydiff == 1)
	    return 0x03;
	 else if (xdiff == 0 && ydiff == 3)
	    return ((y1 == 3 || x2 == 3) ? 0x02 : 0x01);
	 else if ((x2 == 0 && y2 == 0) && xdiff == 2 && ydiff == 3)
	    return ((y1 == 3) ? 0x24 : 0x90);
      }
      ret = small_ret[xdiff*SMALL_ARRAY_SIZE + ydiff];
   }
   else if (!(diff = ydiff - 2*xdiff))
      ret = 0x01;
   else if (diff > 0.) {
      if (diff == 1)
	 ret = 0x83;
      else {
	 static int smaller_ret[] = { 0x81,0xc3,0xc3,0xe7 };
	 ret = smaller_ret[(ydiff - 2 * (xdiff % 2)) % 4];
      }
   }
   else {
      if (diff == -1)
	 ret = 0xc7;
      else if (diff == -2)
	 ret = 0x83;
      else {
	 static int even_smaller_ret[] = { 0x03,0x87,0xcf };
	 ret = even_smaller_ret[(xdiff + ydiff) % 3];
      }
   }
   if (flip) {
      ret = ((ret&0x2)?0x01:0) | ((ret&0x01)?0x02:0) | ((ret&0x80)?0x04:0)
       | ((ret&0x40)?0x08:0) | ((ret&0x20)?0x10:0) | ((ret&0x10)?0x20:0)
       | ((ret&0x08)?0x40:0) | ((ret&0x04)?0x80:0);
   }
   if (rot) {
      ret <<= rot*2;
      ret = (ret&0xff) | (ret >> 8);
   }
   return ret;
}

#define COMBO_S(_a,_b,_c) case _a: count -= (matptr[_b][_c] - 1); break
#define COMBO_BEGIN tmp2_bit = 0x01
#define COMBO_PIECE(_tbit,_bit,_x,_y,_count) \
   if ((_tbit) & 0x1) { \
      switch (tmp2_bit) { \
      case 0x01: count -= (matptr[(_y)+2][(_x)+1] - 1); break; \
      case 0x02: count -= (matptr[(_y)+1][(_x)+2] - 1); break; \
      case 0x04: count -= (matptr[(_y)-1][(_x)+2] - 1); break; \
      case 0x08: count -= (matptr[(_y)-2][(_x)+1] - 1); break; \
      case 0x10: count -= (matptr[(_y)-2][(_x)-1] - 1); break; \
      case 0x20: count -= (matptr[(_y)-1][(_x)-2] - 1); break; \
      case 0x40: count -= (matptr[(_y)+1][(_x)-2] - 1); break; \
      case 0x80: count -= (matptr[(_y)+2][(_x)-1] - 1); break; \
      } \
   } \
   tmp2_bit <<= 1; \

#define COMBO(_bit,_x,_y) \
   if (bit & (_bit)) { \
      s_x = (_x); \
      s_y = (_y); \
      tmp_bit = s_bit = distance_where(s_x, s_y, tox, toy); \
      count = 0; \
      switch (matptr[s_y][s_x]) { \
      case 0: count = 0x40; \
      case 1: case 2: case 3: case 4: case 5: case 6: case 7: \
	 COMBO_BEGIN; \
	 do { \
	    COMBO_PIECE(tmp_bit,&tmp2_bit,s_x,s_y,&count); \
	 } while (tmp_bit >>= 1); \
	 if (switch_count < count) { \
	    switch_x = s_x; \
	    switch_y = s_y; \
	    switch_count = count; \
	    switch_bit = s_bit; \
	 } \
      case 8: break; \
      default: fprintf(stderr, "%d %d %d\n", \
	 s_y, s_x, matptr[s_y][s_x]); exit(1); \
      } \
   } \

void move_out(x, y, tox, toy, inside)
   int x, y, tox, toy, inside;
{
   int bit, j;
   int tmp2_bit;
   int switch_count, switch_bit, count, s_bit;
   int switch_x, switch_y, s_x, s_y, tmp_bit;
   bit = distance_where(x, y, tox, toy);
   moves_c[moves*2] = x;
   moves_c[moves*2+1] = y;
   move_ptr[movep++] = moves++;
   for (j = 0; ; j++) {
      if ((matptr[y][x] += TMARK) > TMARK && inside) {
	 int t_movep = movep-2, t_moves = move_ptr[movep-1]-1;
	 do {
	    if (move_ptr[t_movep] == t_moves) {
		if (moves_c[2*t_moves] == x && moves_c[2*t_moves+1] == y)
		  break;
		--t_movep;
	    }
	    else {
		if (moves_c[2*t_moves] == x && moves_c[2*t_moves+1] == y) {
		  move_again[t_movep] = movep;
		  break;
		}
	    }
	    --t_moves;
	 } while (1);
      }
      switch_count = -127;
      COMBO(0x01, x+1, y+2);
      COMBO(0x02, x+2, y+1);
      COMBO(0x04, x+2, y-1);
      COMBO(0x08, x+1, y-2);
      COMBO(0x10, x-1, y-2);
      COMBO(0x20, x-2, y-1);
      COMBO(0x40, x-2, y+1);
      COMBO(0x80, x-1, y+2);
      bit = switch_bit;
      x = switch_x;
      y = switch_y;
      if (x == tox && y == toy) {
	 break;
      }
      moves_c[moves*2] = x;
      moves_c[moves*2+1] = y;
      moves++;
   }
}

static int redraw(i, add, x1)
   int i, add, x1;
{
   int y, j, k, c, *mpy, *mpy2end, y1, sm;

   if (add) {
      moves = move_ptr[(movep=i)-1];
      k = x1;
      y = move_ptr[movep+1];
      for (j = moves; j < y; j++) {
	 for (c=0; c < checked_custs; c++) {
	    if (moves_c[2*j] == checked_cust[2*c]
	     && moves_c[2*j+1] == checked_cust[2*c+1]) {
	       if (j < k)
		  moves = j;
	       else {
		  y = j;
		  break;
	       }
	    }
	 }
      }
   }
   else {
      moves = x1;
      y = move_ptr[(movep=i)+1];
   }
   sm = moves;
   y1 = moves_c[2*x1+1];
   x1 = moves_c[2*x1];
   memcpy(xtracopy, moves_c+(2*moves), sizeof(int)*2*(j = y - moves));
   move_out(moves_c[2*moves], moves_c[2*moves+1],
      moves_c[2*y], moves_c[2*y+1], 0);
   mpy2end = (mpy = xtracopy) + j*2;
   if ((sm=moves-sm) != j) {
      y = moves;
      sm = j-sm;
      for (moves += sm; moves < total_moves; moves++) {
	 moves_c[(moves-sm)*2] = moves_c[moves*2];
	 moves_c[(moves-sm)*2+1] = moves_c[moves*2+1];
      }
      moves_c[(moves-sm)*2] = 0;
      moves_c[(moves-sm)*2+1] = 0;
      for (moves = 0; moves < degree+1; moves++) {
	 if (move_ptr[moves] > y)
	    move_ptr[moves] -= sm;
      }
   }
   for (j = 0; mpy < mpy2end; mpy += 2) {
      if ((matptr[mpy[1]][*mpy] -= TMARK) > 1)
	 j++;
   }
   if (add && matptr[y1][x1] <= TMARK) {
      checked_cust[2*checked_custs] = x1;
      checked_cust[2*checked_custs+1] = y1;
      checked_custs++;
   }
   return j;
}

static void make_moves()
{
   int i, x1, y1, x2, y2;

   moves = movep = 0;
   for (i = 0; tourcopy[i] != 0; i++)
      ;
   if (i == degree)
      i = 0;
   x1 = xloc[tourcopy[i]];
   y1 = yloc[tourcopy[i]];
   do {
      move_again[movep] = 0;
      y2 = yloc[tourcopy[i+1]];
      x2 = xloc[tourcopy[i+1]];
      move_out(x1, y1, x2, y2, 1);
      x1 = x2;
      y1 = y2;
      if (++i == degree)
	 i = 0;
   } while (tourcopy[i] != 0);

   move_ptr[degree] = total_moves;

   moves_c[moves*2] = moves_c[moves*2+1] = 0;
   checked_custs = 0;
   for (i = 0; i < degree; i++) {
      if (move_again[i] && redraw(i,0,move_ptr[i])
       && move_again[i]-1 != MOVE_LIMIT)
	 redraw(move_again[i]-1,0, move_ptr[move_again[i]-1]);
   }
   for (i = 0; i < degree; i++) {
      x1 = move_ptr[i];
      if (matptr[moves_c[2*x1+1]][moves_c[2*x1]] > TMARK) {
	 redraw(i,1,x1);
      }
   }
}

static int compare_tour(P1, P2, P1end, P2end)
   city_id_t *P1, *P2, *P1end, *P2end;
{
   city_id_t *p1, *p2, s2 = P1end[-1], *p1to;

   for (p1to = P1; p1to < P1end; s2 = *p1to++) {
      if (*P2 == *p1to && (P2[1] == s2 || P2[1] == p1to[1]))
	 break;
   }
   if (!(p1to < P1end))
      return 1;
   if (P2[1] == s2) {
      for (p2 = P2+2, p1 = p1to-1; p1 != p1to; p2++) {
	 if (--p1 < P1)
	    p1 = P1end + (P1 - p1);
	 if (*p1 != *p2)
	    break;
      }
   }
   else {
      for (p2 = P2+2, p1 = p1to+1; p1 != p1to; p2++) {
	 if (++p1 >= P1end)
	    p1 = P1 + (p1 - (P1end - 1));
	 if (*p1 != *p2)
	    break;
      }
   }
   return p2 != P2end;
}

int main (argc, argv)
   int argc; char *argv[];
{
   int *xl, *yl, i, j, x, y;
   int *mpy, *mpy2, *mpy2end;
   sum_t sums[BESTA], sum, save_sum, besta, iters;
   int bestarray[BESTA*(CUST+1)], *bests[BESTA], save_moves, these_moves, stm;
   int *best, bettersj = 0, *movescptr = moves_c, starti;
   int uniq;
   FILE *fp = fopen(argv[1], "r");

   srand(x = SEED);
   xloc[0] = yloc[0] = tourcopy[0] = 0;
   for (degree = 1; 2 == fscanf(fp, "%d%d", xloc+degree, yloc+degree); degree++)
      tourcopy[degree] = degree;
   xloc[degree] = yloc[degree] = 0;
   besta = BESTA_VAL(degree);
   iters = ITERS_VAL(degree);
   if (degree > CUST+1) {
		fprintf(stderr, "There are Too many customers!\n");
		exit(1);
	}
   matptr = matrixptr + BEVEL;
   for (i = 0; i < degree; i++) {
      mpy = (matptr[i] = &(matrix[i+BEVEL][BEVEL]));
      x = xloc[i]; y = yloc[i]; xl = xloc; yl = yloc;
      for (mpy2end = (mpy2 = mpy) + degree; mpy2 < mpy2end; mpy2++, xl++, yl++)
	 *mpy2 = distance(x, y, *xl, *yl);
      mpy[i] = MAX_COST;
   }
   for (j = 0; j < besta; j++) {
      bests[j] = bestarray + (j*(CUST+1));
      sums[j] = MAX_SUM;
   }
   memcpy(checked_cust, tourcopy, sizeof(city_id_t)*degree);
   for (j = 0; j < iters; j++) {
      memcpy(tourcopy, checked_cust, sizeof(city_id_t)*degree);
      for (i = 0; i < degree; i++) {
	 x = degree-1-(rand()%(degree-i));
	 y = tourcopy[x];
	 tourcopy[x] = tourcopy[i];
	 tourcopy[i] = y;
      }
      memcpy(checked_cust, tourcopy, sizeof(city_id_t)*degree);
      tourcopy[degree] = tourcopy[0];
      nudge();
      for (sum=0, i=0; i sum) {
	 best = bests[0];
	 save_sum = sums[0];
	 uniq = 1;
	 for (starti = 0, i = 1; i < besta; i++) {
	    if (sums[i] < sum)
	       break;
	    else if (sums[i] == sum) {
	       if (starti == 0)
		  starti = i;
	       if (starti+besta/3 < i || !compare_tour(tourcopy, bests[i],
		tourcopy+degree, bests[i]+degree)) {
		  uniq = 0;
		  break;
	       }
	       sums[i-1] = sums[i];
	       bests[i-1] = bests[i];
	    }
	    else {
	       sums[i-1] = sums[i];
	       bests[i-1] = bests[i];
	    }
	 }
	 if (!uniq) {
	    for (i--; i > 0; i--) {
	       sums[i] = sums[i-1];
	       bests[i] = bests[i-1];
	    }
	    bests[0] = best;
	    sums[0] = save_sum;
	    continue;
	 }
	 sums[i-1] = sum;
	 memcpy(bests[i-1] = best, tourcopy, sizeof(city_id_t)*degree);
      }
   }
   save_sum = MAX_SUM;
   for (j = besta; --j >= 0 && sums[j] != MAX_SUM; ) {
      memcpy(tourcopy, bests[j], sizeof(city_id_t)*degree);
      tourcopy[degree] = tourcopy[0];
      if (grind(1)) {
	 if (nudge()) if (grind(0)) if (nudge()) if (grind(0)) nudge();
      }
      for (sum=0, i=0; i= sum) {
	 if (save_sum > sum) {
	    bettersj = 0;
	    save_sum = sum;
	 }
	 memcpy(bests[(besta-1-bettersj++)],tourcopy,sizeof(city_id_t)*degree);
      }
   }
   for (j = -1; j >= -BEVEL; j--) {
      matptr[j] = &(matrix[BEVEL+j][BEVEL]);
      for (i = -1; i >= -BEVEL; i--)
	 matptr[j][i] = 8;
   }
   for (i = 0; i < GRIDSIZE; i++) {
      mpy = (matptr[i] = &(matrix[i+BEVEL][BEVEL]));
      for (j = 0; j < BEVEL; j++)
	 mpy[-j-1] = matrix[j][i+BEVEL] = 8;
      for (mpy2end = (mpy2 = mpy) + GRIDSIZE; mpy2 < mpy2end; )
	 *mpy2++ = 0;
   }
   stm = total_moves = save_sum;
   save_moves = 0;
   bettersj *= 2;
   do {
      best = bests[besta-1-(--bettersj)/2];
      for (j = besta-1-bettersj/2; ++j < besta; ) {
	 if (!compare_tour(best, bests[j], best+degree, bests[j]+degree))
	    break;
      }
      if (j < besta)
	 continue;
      if (bettersj % 2)
	 memcpy(tourcopy, best, sizeof(city_id_t)*degree);
      else {
	 for (i = degree-1, moves = 0; moves < degree; moves++, i--)
	    tourcopy[i] = best[moves];
      }
      tourcopy[degree] = tourcopy[0];
      make_moves();
      these_moves = move_ptr[degree];
      if (these_moves <= stm) {
	 if (these_moves < stm) {
	    stm = these_moves;
	    save_moves = 0;
	 }
      }
      else {
	 for (moves = these_moves-1; moves >= 0; moves--)
	    matptr[moves_c[moves*2+1]][moves_c[moves*2]] -= TMARK;
	 continue;
      }
      for (moves = 0; moves < stm; moves++) {
	 if ((matptr[moves_c[moves*2+1]][moves_c[moves*2]] -= TMARK) > 0)
	    these_moves--;
      }
      if (save_moves < these_moves) {
	 save_moves = these_moves;
	 movescptr = moves_bak;
	 for (moves = 0; moves < stm+1; moves++) {
	    moves_bak[moves*2] = moves_c[moves*2];
	    moves_bak[moves*2+1] = moves_c[moves*2+1];
	 }
      }
   } while (bettersj);
   for (moves = 0; moves < stm+1; moves++) {
      fprintf(stdout, "%d %d\n", movescptr[moves*2], movescptr[moves*2+1]);
   }
   fclose(fp);
   fclose(stdout);
   return 0;
}