救救鼠鼠，黄题不会做了

//暴力：得到1所在的联通块，得到n所在的联通块，放到两个数组里，然后枚举其他点，连一下
//如果在同一个联通块内花费为0 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,m;
int fa[100010];
int find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
vector<int> g1,g2;
signed main()
{
	cin>>T;
	while(T--)
	{
		g1.clear();
		g2.clear();
		scanf("%lld%lld",&n,&m);
		for(int i=1;i<=n;i++)
		{
			fa[i]=i;
		}
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%lld%lld",&u,&v);
			int f1=find(u);
			int f2=find(v);
			if(f1==f2)
			continue;
			fa[f2]=f1;
		}
		int flag1=find(1);//找到1所在联通块的代表元素
		int flag2=find(n);//找到n所在联通块的代表元素
		if(flag1==flag2)
		{
			printf("0\n");
			continue;
		} 
		for(int i=1;i<=n;i++)
		{
			if(find(i)==flag1)//与1同属一个联通块
			g1.push_back(i);
			if(find(i)==flag2)
			g2.push_back(i); 
		}
		int ans=1e18;
		for(int i=1;i<=n;i++)//枚举一个中间点，与1所在的联通块内的一点相连，再与n所在的联通块内的一点相连 
		{
			int sum=0,sum1=0,sum2=0;
			//lower_bound找到大于等于它的数的位置p，比较p和p-1哪个差值更小即可
			//往n所在的联通块连边 
			int p2=lower_bound(g2.begin(),g2.end(),i)-g2.begin();
			if(p2-1>=0)
			sum2=min((i-g2[p2])*(i-g2[p2]),(i-g2[p2-1])*(i-g2[p2-1]));
			else sum2=(i-g2[p2])*(i-g2[p2]);
			//往1所在的联通块连边 
			int p1=lower_bound(g1.begin(),g1.end(),i)-g1.begin();
			if(p1-1>=0)
			sum1=min((i-g1[p1])*(i-g1[p1]),(i-g1[p1-1])*(i-g1[p1-1]));
			else sum1=(i-g1[p1])*(i-g1[p1]);
			//
			if(find(i)==flag1)//和1同属一个联通块 
			sum=sum2;
			else if(find(i)==flag2)//和n同属一个联通块 
			sum=sum1;
			else sum=sum1+sum2;
			ans=min(ans,sum);
		} 
		printf("%lld\n",ans);
	}
	return 0;
}