60pts

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;

int T,n,m,fa[N],u,v,ans1[N],ansn[N];
int vis[N];
inline int f(int x){
	if(fa[x]==x) return x;
	fa[x]=f(fa[x]);
	return fa[x];
}

signed main(){
//	freopen("connecting2.in","r",stdin);
//	freopen("connecting.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T;
	for(int zsq=1;zsq<=T;zsq++){
		cin>>n>>m;
		for(int i=1;i<=n;i++) fa[i]=i;
		memset(ans1,0x3f,sizeof(ans1));
		memset(ansn,0x3f,sizeof(ansn));
		for(int i=1;i<=m;i++){
			cin>>u>>v;
			int uf=f(u);
			int vf=f(v);
			if(uf!=vf) fa[uf]=vf;
		}
		int f1=f(1),fn=f(n);
		if(f1==fn){
			puts("0");
			continue;
		}
		ans1[f1]=0;
		ansn[fn]=0;
		vector<int> a,b;
		for(int i=1;i<=n;i++){
			int fi=f(i);
			if(fi==f1) a.push_back(i);
			if(fi==fn) b.push_back(i);
		}
		sort(a.begin(),a.end());//a存放1所在连通分量
		sort(b.begin(),b.end());//b存放n所在连通分量
		//从每个点去更新每一个分量 
		for(int i=1;i<=n;i++){
			int fi=f(i);
			if(fi!=f1){
				int pos1=upper_bound(a.begin(),a.end(),i)-a.begin();
				if(pos1<a.size()) ans1[fi]=min(ans1[fi],(i-a[pos1])*(i-a[pos1]));
				if(pos1-1>=0) ans1[fi]=min(ans1[fi],(i-a[pos1-1])*(i-a[pos1-1]));
			}
			if(fi!=fn){
				int posn=upper_bound(b.begin(),b.end(),i)-b.begin();
				if(posn<b.size()) ansn[fi]=min(ansn[fi],(i-b[posn])*(i-b[posn])); 
				if(posn-1>=0) ansn[fi]=min(ansn[fi],(i-b[posn-1])*(i-b[posn-1]));
			}
		}
		int ans=(n-1)*(n-1);
		for(int i=1;i<=n;i++) ans=min(ans,ans1[i]+ansn[i]);
		cout<<ans<<"\n";
	}
	return 0;
}