思路：考虑把图当成并查集维护。

如果 $1,n$ 属于同一个并查集：答案是 $0$。

如果 $1,n$ 不在同一个并查集：

假设 $1$ 属于 $a$，$n$ 属于 $b$。

找到差最小的点对 $(i,j)$ 使得 $i$ 在 $a$ 中，$j$ 在 $b$ 中。

此时如果 $|i-j|=1$ 那答案是 $1$。

否则找平均数 $k\lfloor(i+j)\div 2\rfloor$。

然后连接 $(i,k),(k,j)$。

显然 $k$ 不会属于 $a,b$ 因为如果属于，点对 $(i,j)$ 就求错了。

#include<bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
using namespace std;
constexpr int N=500001;
int T,n,m,f[N];
set<int>s[N];
vector<pair<int,int> >vec;
int find_near(int i,int j){
	int ans=0x3f3f3f3f;
	vec.clear();
	for(auto p:s[i])
		vec.push_back({p,i});
	for(auto p:s[j])
		vec.push_back({p,j});
	sort(ALL(vec));
	for(int lasti=0x3f3f3f3f,lastj=0x3f3f3f3f,k=0;k<(int)vec.size();k++){
		if(vec[k].second==i){
			lasti=vec[k].first;
			if(lastj==0x3f3f3f3f)
				continue;
			ans=min(ans,abs(lastj-lasti));
		}
		else{
			lastj=vec[k].first;
			if(lasti==0x3f3f3f3f)
				continue;
			ans=min(ans,abs(lastj-lasti));
		}
	}
	return ans;
} 
int findfa(int x){
	if(f[x]==x)
		return x;
	return f[x]=findfa(f[x]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	for(cin>>T;T;--T){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			s[i].clear();
			f[i]=i;
		}
		for(int i=1,a,b,u,v;i<=m;i++){
			cin>>a>>b;
			u=min(findfa(a),findfa(b)),v=max(findfa(a),findfa(b));
			if(u==v)
				continue;
			f[v]=f[u];
		}
		for(int i=1;i<=n;i++)
			s[findfa(i)].insert(i);
		if(findfa(1)==findfa(n)){
			cout<<"0\n";
			continue;
		}
		int k=find_near(findfa(1),findfa(n)),t1=k/2,t2=k-t1;
		cout<<min(t1*t1+t2*t2,k*k)<<'\n';
	}
    return 0;
}