以终点为开始点，bfs扩展，那么第一次扩展到的点就是离终点的最小距离

import java.util.*;
import java.io.*;

public class Main{
	static final int N = 2010, INF = 0x3f3f3f3f, M = N * N + N;
	static int n, m;
	static List<Integer>[] list = new ArrayList[M];
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int[] dist = new int[M];
	static boolean[] st = new boolean[M];
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] str = br.readLine().split(" ");
		n = Integer.parseInt(str[0]);
		m = Integer.parseInt(str[1]);
		
		for(int i=0 ; i<M ; i++)
			list[i] = new ArrayList<>();
		
		for(int i=0 ; i<m ; i++)
		{
			str = br.readLine().split(" ");
			int x1 = Integer.parseInt(str[0]);
			int y1 = Integer.parseInt(str[1]);
			int x2 = Integer.parseInt(str[2]);
			int y2 = Integer.parseInt(str[3]);
			x1--;
			y1--;
			x2--;
			y2--;
			
			list[get(x1, y1)].add(get(x2, y2));
			list[get(x2, y2)].add(get(x1, y1));
		}
		
		bfs();
		
		double res = 0;
		
		for(int i=0 ; i<n ; i++)
			for(int j=0 ; j<n ; j++)
				res += dist[get(i, j)];
		
		res /= n * n;
		
		System.out.printf("%.2f", res);
	}
	
	public static void bfs()
	{
		Arrays.fill(dist, INF);
		
		Queue<Integer> q = new LinkedList<>();
		q.add(get(n - 1, n - 1));
		dist[get(n - 1, n - 1)] = 0;
		
		while(q.size() > 0)
		{
			int t = q.remove();
			int x = t / n;
			int y = t % n;    
			
			st[t] = false;
			
			for(int v: list[t])
			{
				int a = v / n;
				int b = v % n;
				
				if(dist[get(a, b)] > dist[get(x, y)] + 1)
				{
					dist[get(a, b)] = dist[get(x, y)] + 1;
					
					if(!st[get(a, b)])
					{
						q.add(get(a, b));
						st[get(a, b)] = true;
					}
					
				}
			}
			
			for(int i=0 ; i<4 ; i++)
			{
				int a = x + dx[i];
				int b = y + dy[i];
				
				if(a < 0 || a >= n || b < 0 || b >= n) continue;
				
				if(dist[get(a, b)] > dist[get(x, y)] + 1)
				{
					dist[get(a, b)] = dist[get(x, y)] + 1;
					
					if(!st[get(a, b)])
					{
						q.add(get(a, b));
						st[get(a, b)] = true;
					}
				}
			}
		}
	}
	
	public static int get(int x, int y)
	{
		return x * n + y;
	}
}