思路：求出所有的连通块，枚举中间连通块，求从1到中间连通块再到n的最小值即为答案。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,m,sum=1,ed,mi[100005];
bool vis[100005];
vector<int> v[100005],ltx[100005];
void dfs(int x,int sett){
	vis[x]=1;
	ltx[sett].push_back(x);
	if(x==n){
		ed=sett;
	}
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i];
		if(!vis[y]){
			dfs(y,sett);
		}
	}
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		sum=1;
		for(int i=1;i<=n;i++){
			v[i].clear();
		}
		for(int i=1;i<=n;i++){
			ltx[i].clear();
		}
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++){
			mi[i]=LONG_LONG_MAX;
		}
		bool flag=0;
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			v[x].push_back(y);
			v[y].push_back(x);
			if(x==1&&y==n){
				flag=1;
			}
		}
		if(flag){
			cout<<"0\n";
			continue;
		}
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				dfs(i,sum);
				sort(ltx[sum].begin(),ltx[sum].end());
				sum++;
			}
		}
		if(sum==2){
			cout<<"0\n";
			continue;
		}
		for(int i=2;i<sum;i++){
			int t=0;
			for(int j=ltx[1].size()-1;j>=0;j--){
				bool flag=0;
				while(t<ltx[i].size()&&ltx[i][t]<ltx[1][j]){
					t++;
					flag=1;
				}
				if(t!=0){
					mi[i]=min(mi[i],(ltx[i][t-1]-ltx[1][j])*(ltx[i][t-1]-ltx[1][j]));
				}
				if(t!=ltx[i].size()){
					mi[i]=min(mi[i],(ltx[i][t]-ltx[1][j])*(ltx[i][t]-ltx[1][j]));
				}
				if(!flag){
					break;
				}
			}
		}
		int minn=LONG_LONG_MAX;
		for(int i=2;i<sum;i++){
			if(i==ed){
				minn=min(minn,mi[i]);
				continue;
			}
			int t=0;
			for(int j=ltx[ed].size()-1;j>=0;j--){
				bool flag=0;
				while(t<ltx[i].size()&&ltx[i][t]<ltx[ed][j]){
					t++;
					flag=1;
				}
				if(t!=0){
					minn=min(minn,mi[i]+(ltx[i][t-1]-ltx[ed][j])*(ltx[i][t-1]-ltx[ed][j]));
				}
				if(t!=ltx[i].size()){
					minn=min(minn,mi[i]+(ltx[i][t]-ltx[ed][j])*(ltx[i][t]-ltx[ed][j]));
				}
				if(!flag){
					break;
				}
			}
		}
		cout<<minn<<"\n";
	}
	return 0;
}