#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+5;
int n,m;
int fa[N],siz[N];
int find(int x){return (x==fa[x]?x:fa[x]=find(fa[x]));}
void hb(int x,int y)
{
	x=find(x),y=find(y);
	if(siz[x]>siz[y])fa[y]=x,siz[x]+=siz[y];
	else fa[x]=y,siz[y]+=siz[x];
}
vector<int>a[N];
long long find_min(int k1,int k2)
{
	long long minx=LLONG_MAX;
	for(auto &i:a[k1])
	{
		int x=lower_bound(a[k2].begin(),a[k2].end(),i)-a[k2].begin();
		if(x==0)minx=min(minx,(long long)(a[k2][x]-i)*(long long)(a[k2][x]-i));
		long long x1=a[k2][x],x2=a[k2][x-1];
		minx=min(minx,min((long long)(x1-i)*(long long)(x1-i),(long long)(x2-i)*(long long)(x2-i)));
	}
	return minx;
}
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	int TT;cin>>TT;
	while(TT--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1,a[i].clear();
		for(int i=1;i<=m;i++)
		{
			int u,v;cin>>u>>v;
			hb(u,v);
		}
		for(int i=1;i<=n;i++)
		a[find(i)].push_back(i);
		for(int i=1;i<=n;i++)sort(a[i].begin(),a[i].end());
		int k1=find(1),kn=find(n);
		if(k1==kn)
		{
			cout<<0<<'\n';
			continue;
		}
		long long ans=find_min(k1,kn);
		for(int i=1;i<=n;i++)
		if(!a[i].empty()&&i!=k1&&i!=kn)ans=min(ans,find_min(k1,i)+find_min(i,kn));
		cout<<ans<<'\n';
	}
	return 0;
}