#include <iostream>
#include <stdio.h>
using namespace std;

int n, p;

int Abs(int a, int b){
	if(a-b>0) return a-b;
	return b-a;
}

int xs[10086], ys[10086], xe[10086], ye[10086];

int main() {
	int cnt = 0;
	while(cin >> n){
		cnt++;
		if(n == 0) return 0;
		cin >> p;
		for(int i = 0; i < p; i++){
			int tmp, tmp1;
			cin >> tmp >> tmp1;
			tmp--, tmp1--;
			xs[i] = tmp/n, ys[i] = tmp%n, xe[i] = tmp1/n, ye[i] = tmp1%n;
		}
		int mn = 2147483647;
		int agr = 0;
		for(int i = 0; i < p; i++) agr += Abs(xs[i], xe[i])+Abs(ys[i],ye[i])+1;
		if(agr<mn) mn = agr;
		agr = 0;
		for(int i = 0; i < p; i++) agr += Abs(xs[i], xe[i])+Abs(ys[i],n-1-ye[i])+1;
		if(agr<mn) mn = agr;
		agr = 0;
		for(int i = 0; i < p; i++) agr += Abs(xs[i], n-1-xe[i])+Abs(ys[i],ye[i])+1;
		if(agr<mn) mn = agr;
		agr = 0;
		for(int i = 0; i < p; i++) agr += Abs(xs[i], n-1-xe[i])+Abs(ys[i],n-1-ye[i])+1;
		if(agr<mn) mn = agr;
		agr = 0;
		for(int i = 0; i < p; i++) agr += Abs(xs[i], ye[i])+Abs(ys[i],xe[i])+1;
		if(agr<mn) mn = agr;
		agr = 0;
		for(int i = 0; i < p; i++) agr += Abs(xs[i], ye[i])+Abs(ys[i],n-1-xe[i])+1;
		if(agr<mn) mn = agr;
		agr = 0;
		for(int i = 0; i < p; i++) agr += Abs(xs[i], n-1-ye[i])+Abs(ys[i],xe[i])+1;
		if(agr<mn) mn = agr;
		agr = 0;
		for(int i = 0; i < p; i++) agr += Abs(xs[i], n-1-ye[i])+Abs(ys[i],n-1-xe[i])+1;
		if(agr<mn) mn = agr;
		double ave = mn * 1.0 / p;
		printf("Scenario %d: smallest average = %.4lf\n\n", cnt, ave);
	}
	return 0;
}