//mesh.cpp
//pgmr: T Feil
//Meshing Meshes problem
//2002 EC ACM regional contest

#include <iostream.h>
#include <iomanip.h>

int R[10001], C[10001], F[10001],S[10001];

int abs(int n){
  if(n<0) return (-1*n);
  else
    return n;
}

void UpdateCount(int &count,  int Row[],  int Col[], int m){
  int c=m, i;
 
  for(i=0;i<m;i++)
    c += abs(R[F[i]]-Row[S[i]]) + abs(C[F[i]]-Col[S[i]]);

  if(c<count) count = c;
}

void main(){
  int n, m,  i, j, Row[10001], Col[10001], c, count;
  int num=1;

  cin>>n;

  while(n>0) {
    c=1;
    for(i=0;i<n;i++)
      for(j=0;j<n;j++){
        R[c]=i; C[c]=j; c++;}

    //get pairs
    cin>>m;
    for(i=0;i<m;i++)
      cin>>F[i]>>S[i];

    //establish  count
    count=m;
    for(i=0;i<m;i++)
      count += abs(R[F[i]]-R[S[i]]) + abs(C[F[i]]-C[S[i]]);

    //now check all rotations/flips
    c=1;
    for(i=n-1;i>=0;i--)
      for(j=0;j<n;j++){
        Row[c]=i; Col[c]=j; c++;}

    UpdateCount(count,Row,Col,m);

    c=1;
    for(j=0;j<n;j++)
      for(i=n-1;i>=0;i--){
        Row[c]=i; Col[c]=j; c++;}

    UpdateCount(count,Row,Col,m);
   
    c=1;
    for(i=0;i<n;i++)
      for(j=n-1;j>=0;j--){
        Row[c]=i; Col[c]=j; c++;}

    UpdateCount(count,Row,Col,m);
   
    c=1;
    for(j=n-1;j>=0;j--)
      for(i=0;i<n;i++){
        Row[c]=i; Col[c]=j; c++;}

    UpdateCount(count,Row,Col,m);
     
    c=1;
    for(j=n-1;j>=0;j--)
      for(i=n-1;i>=0;i--){
        Row[c]=i; Col[c]=j; c++;}

    UpdateCount(count,Row,Col,m);
     
    c=1;
    for(i=n-1;i>=0;i--)
      for(j=n-1;j>=0;j--){
        Row[c]=i; Col[c]=j; c++;}

    UpdateCount(count,Row,Col,m);
     
    c=1;
    for(j=0;j<n;j++)
      for(i=0;i<n;i++){
        Row[c]=i; Col[c]=j; c++;}

    UpdateCount(count,Row,Col,m);
     
    if(num>1) cout<<endl;
    cout<<"Scenario "<<setw(1)<<num++<<": smallest average = ";
    cout<<setprecision(4)<<setiosflags(ios::fixed);
    cout<<(double)count/m<<endl;

  cin>>n;
  }
}