#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
int t,n,m,u,v,zuo[200005],you[200005],id[200005],vis[200005],cnt,bigRex;
vector<int>ve[200005],ve2[200005];
void dfs(int x)
{
	zuo[x] = you[x] = x,vis[x] = 1;
	id[x] = cnt;
	for(int i = 0;i < ve[x].size();i ++)
		if(!vis[ve[x][i]])
		{
			vis[ve[x][i]] = 1;
			dfs(ve[x][i]);
			zuo[x] = min(zuo[x],zuo[ve[x][i]]);
			you[x] = max(you[x],you[ve[x][i]]);
		}
}
int Minn(int x,int y,int z)
{
	return min((z - y) * (z - y),(z - x) * (z - x));
}
signed main()
{
	cin >> t;
	vector<int>::iterator kk,kk2;
	while(t --)
	{
		cin >> n >> m;
		int zhen = 1e12;
		cnt = 0;
		for(int i = 1;i <= n;i ++)
			ve[i].clear(),ve2[i].clear(),vis[i] = id[i] = zuo[i] = you[i] = 0;
		for(int i = 1;i <= m;i ++)
		{
			cin >> u >> v;
			ve[u].push_back(v),ve[v].push_back(u);
		}
		for(int i = 1;i <= n;i ++)
			if(!vis[i])cnt ++,dfs(i);
		if(you[1] == n)
		{
			cout << "0\n";
			continue ;
		}
		for(int i = 1;i <= n;i ++)
		{
			ve2[id[i]].push_back(i);
			if(i == n)bigRex = id[i];
		}
 		for(int i = 1;i <= cnt;i ++)
		{
			int ans = 1e12,ans2 = 1e12;
			for(int j = 0;j < ve2[i].size();j ++)
			{
				int q = ve2[i][j];
				kk = lower_bound(ve2[1].begin(),ve2[1].end(),q),kk2 = upper_bound(ve2[1].begin(),ve2[1].end(),q);
				int kl = distance(ve2[1].begin(),kk),kl2 = distance(ve2[1].begin(),kk2);
				if(kl >= ve2[1].size())kl --;
				if(kl2 >= ve2[1].size())kl2 --;
				ans = min(ans,Minn(ve2[1][kl],ve2[1][kl2],q));
			}
			for(int j = 0;j < ve2[i].size();j ++)
			{
				int q = ve2[i][j];
				kk = lower_bound(ve2[bigRex].begin(),ve2[bigRex].end(),q),kk2 = upper_bound(ve2[bigRex].begin(),ve2[bigRex].end(),q);
				int kl = distance(ve2[bigRex].begin(),kk),kl2 = distance(ve2[bigRex].begin(),kk2);
				if(kl >= ve2[bigRex].size())kl --;
				if(kl2 >= ve2[bigRex].size())kl2 --;
				ans2 = min(ans2,Minn(ve2[bigRex][kl],ve2[bigRex][kl2],q));
			}
			zhen = min(zhen,ans + ans2);
		
		cout << zhen << '\n';
	}
}