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

#define MAX_N 100

typedef struct {
  int row, col;
} Location;

int dist(Location l1, Location l2)
{
  return abs(l1.row - l2.row) + abs(l1.col - l2.col) + 1;
}

void gen_plug(Location plug[MAX_N*MAX_N+1], int n)
{
  int i, j, k;
  k = 1;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      plug[k].row = i+1;
      plug[k++].col = j+1;
    }
  }
}

void get_loc(int temp[MAX_N][MAX_N], Location socket[8][MAX_N*MAX_N+1],
	     int n, int k)
{
  int i, j;

  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      socket[k][temp[i][j]].row = i+1;
      socket[k][temp[i][j]].col = j+1;
    }
  }
}

void gen_socket(Location socket[8][MAX_N*MAX_N+1], int n)
{
  int temp[MAX_N][MAX_N];
  int i, j, k;

  k = 1;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      temp[i][j] = k++;
    }
  }
  get_loc(temp, socket, n, 0);
  
  k = 1;
  for (j = n-1; j >= 0; j--) {
    for (i = 0; i < n; i++) {
      temp[i][j] = k++;
    }
  }
  get_loc(temp, socket, n, 1);

  k = 1;
  for (i = n-1; i >= 0; i--) {
    for (j = n-1; j >= 0; j--) {
      temp[i][j] = k++;
    }
  }
  get_loc(temp, socket, n, 2);

  k = 1;
  for (j = 0; j < n; j++) {
    for (i = n-1; i >= 0; i--) {
      temp[i][j] = k++;
    }
  }
  get_loc(temp, socket, n, 3);

  k = 1;
  for (i = 0; i < n; i++) {
    for (j = n-1; j >= 0; j--) {
      temp[i][j] = k++;
    }
  }
  get_loc(temp, socket, n, 4);
  
  k = 1;
  for (j = n-1; j >= 0; j--) {
    for (i = n-1; i >= 0; i--) {
      temp[i][j] = k++;
    }
  }
  get_loc(temp, socket, n, 5);

  k = 1;
  for (i = n-1; i >= 0; i--) {
    for (j = 0; j < n; j++) {
      temp[i][j] = k++;
    }
  }
  get_loc(temp, socket, n, 6);

  k = 1;
  for (j = 0; j < n; j++) {
    for (i = 0; i < n; i++) {
      temp[i][j] = k++;
    }
  }
  get_loc(temp, socket, n, 7);
}

double avg_dist(Location plug[MAX_N*MAX_N+1], Location socket[MAX_N*MAX_N+1],
		int from[MAX_N*MAX_N], int to[MAX_N*MAX_N], int m)
{
  int i, sum = 0;

  for (i = 0; i < m; i++) {
    sum += dist(plug[from[i]], socket[to[i]]);
  }
  return (double)sum/m;
}

int main(void)
{
  Location socket[8][MAX_N*MAX_N+1], plug[MAX_N*MAX_N+1];
  int from[MAX_N*MAX_N], to[MAX_N*MAX_N];
  int n, m, num, i;
  double avg, best_avg;

  num = 1;
  while (scanf("%d", &n) == 1 && n) {
    if (num > 1) {
      printf("\n");
    }
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
      scanf("%d %d", from+i, to+i);
    }
    gen_plug(plug, n);
    gen_socket(socket, n);

    best_avg = avg_dist(plug, socket[0], from, to, m);
    for (i = 1; i < 8; i++) {
      avg = avg_dist(plug, socket[i], from, to, m);
      if (avg < best_avg) {
	best_avg = avg;
      }
    }

    printf("Scenario %d: smallest average = %.4f\n", num++, best_avg);
  }
  return 0;
}