// Arup Guha
// 7/22/2022
// Solution to 2021 USACO December Silver Problem: Convoluted Intervals

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

public class connect {

	public static void main(String[] args) throws Exception {
	
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		int nC = Integer.parseInt(stdin.readLine());
		
		// Process all cases.
		for (int loop=0; loop<nC; loop++) {
		
			// Read in data, use disjoint set to id all sets of connected fields.
			StringTokenizer tok = new StringTokenizer(stdin.readLine());
			int n = Integer.parseInt(tok.nextToken());
			int e = Integer.parseInt(tok.nextToken());
			djset dj = new djset(n);
			for (int i=0; i<e; i++) {
				tok = new StringTokenizer(stdin.readLine());
				int u = Integer.parseInt(tok.nextToken())-1;
				int v = Integer.parseInt(tok.nextToken())-1;
				dj.union(u,v);
			}
			
			// Store each djset root.
			HashSet<Integer> leaders = new HashSet<Integer>();
			int[] lead = new int[n];
			for (int i=0; i<n; i++) {
				lead[i] = dj.find(i);
				leaders.add(lead[i]);
			}
			
			// Map each root to a unique integer 0 to size-1 (new value of id).
			int id = 0;
			HashMap<Integer,Integer> mappedLeaders = new HashMap<Integer,Integer>();
			for (Integer x: leaders)
				mappedLeaders.put(x, id++);
			int size = mappedLeaders.size();
			
			// My lists.
			ArrayList<Integer>[] lists = new ArrayList[id];
			for (int i=0; i<id; i++) lists[i] = new ArrayList<Integer>();
			
			// For lists of groups - sort items.
			for (int i=0; i<n; i++) {
				int num = mappedLeaders.get(lead[i]);
				lists[num].add(i);
			}
			for (int i=0; i<lists.length; i++)
				Collections.sort(lists[i]);
			
			// Get leaders.
			int sList = mappedLeaders.get(lead[0]);
			int eList = mappedLeaders.get(lead[n-1]);
			
			// Get minimum cost from sList to all other lists.
			long[] sCost = new long[size];
			for (int i=0; i<size; i++) {
				if (i == sList) continue;
				sCost[i] = minCost(lists[sList], lists[i]);
			}
			
			// Same for eList.
			long[] eCost = new long[size];
			for (int i=0; i<size; i++) {
				if (i == eList) continue;
				eCost[i] = minCost(lists[eList], lists[i]);
			}
			
			// Try each point as an intermediary point.
			long res = sCost[eList];
			for (int i=0; i<size; i++)
				res = Math.min(res, sCost[i]+eCost[i]);
			System.out.println(res);
		}
	}
	
	// Returns min of |a[i]-b[j]| in sorted lists a and b. a could be longer list.
	public static long minCost(ArrayList<Integer> a, ArrayList<Integer> b) {
		
		// This is valid.
		long res = Math.abs(a.get(0) - b.get(0));
			
		// Update if better.
		for (Integer x: b) {
			long best = binsearch(x, a);
			res = Math.min(res, best);
		}
		
		// Ta da!
		return res*res;		
	}
	
	// Returns the nearest integer to x in a.
	public static long binsearch(Integer x, ArrayList<Integer> a) {
		
		// Binary searching for greatest item less than or equal to x.
		int low = 0, high = a.size()-1; 
		while (low < high) {
			int mid = (low+high+1)/2;
			if (a.get(mid) > x)
				high = mid-1;
			else
				low = mid;
		}
		
		// Tricky case - a[0] is greater than x, so need the absolute value.
		long tmp = Math.abs(x - a.get(low));
		
		// Go higher now, if possible. The last line is probably overkill.
		if (low+1<a.size()) tmp = Math.min(tmp, a.get(low+1)-x);
		if (low-1>=0) tmp = Math.min(tmp, Math.abs(a.get(low-1)-x));
		return tmp;
	}
}

/* Disjoint Set */
class djset {

	public int n;
	public int[] par;
	
	public djset(int myn) {
		n = myn;
		par = new int[n];
		for (int i=0; i<n; i++)
			par[i] = i;
	}
	
	public int find(int v) {
		if (par[v] == v) return v;
		return par[v] = find(par[v]);
	}
	
	public boolean union(int u, int v) {
		u = find(u);
		v = find(v);
		if (u == v) return false;
		par[v] = u;
		return true;
	}
	
}