#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x<<1) + (x<<3) + (ch^48);
		ch = getchar();
	}
	return x * f;
}
const int N = 1e5 + 1;
vector<int> e[N];
bool vis[N];
inline bool checkZero(int target){
	memset(vis, false, sizeof(vis));
	queue<int> q;
	vis[1] = true;
	q.push(1);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		if(u == target) return true;
		for(auto v : e[u]){
			if(!vis[v]){
				vis[v] = true;
				q.push(v);
			}
		}
	}
	return false;
}
inline vector<int> to_where(int start){
	memset(vis, false, sizeof(vis));
	vector<int> res;
	res.push_back(start);
	queue<int> q;
	vis[1] = true;
	q.push(start);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto v : e[u]){
			if(!vis[v]){
				vis[v] = true;
				q.push(v);
				res.push_back(v);
			}
		}
	}
	return res;
}
int tot = 0, color[N], s[N], t[N];
inline void bfs(int start, int c){
	queue<int> q;
	q.push(start);
	color[start] = c;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto v : e[u]){
			if(!color[v]){
				color[v] = c;
				q.push(v);
			}
		}
	}
	return;
}
inline int find(vector<int> v, int target){
	int pos2 = lower_bound(v.begin(), v.end(), target) - v.begin();
	int pos1 = pos2 - 1;
	pos1 = max(pos1, 0ll);
	pos2 = min(pos2, (int)v.size() - 1ll);
	return min((v[pos1]-target)*(v[pos1]-target), (v[pos2]-target)*(v[pos2]-target));
}
inline void Solve(){
	tot = 0;
	memset(color, 0, sizeof(color));
	int n = read(), m = read();
	for(int i = 1; i <= n; i++) e[i].clear();
	for(int i = 1; i <= m; i++){
		int u = read(), v = read();
		e[u].push_back(v);
		e[v].push_back(u);
	}
	if(checkZero(n)){
		cout << 0 << endl;
		return;
	}
	for(int i = 1; i <= n; i++){
		if(!color[i]){
			bfs(i, ++tot);
		}
	}
	vector<int> group[2];
	group[0] = to_where(1);
	group[1] = to_where(n);
	sort(group[0].begin(), group[0].end());
	sort(group[1].begin(), group[1].end());
	for(int i = 1; i <= n; i++) s[i] = t[i] = 1e18;
	for(int i = 1; i <= n; i++) s[color[i]] = min(s[color[i]], find(group[0], i));
	for(int i = 1; i <= n; i++) t[color[i]] = min(t[color[i]], find(group[1], i));
	//for(int i = 1; i <= n; i++){
	//	cout << i << " " << color[i] << " " << s[color[i]] << endl;
	//}
	//cout << endl;
	//for(int i = 1; i <= n; i++){
	//	cout << i << " " << color[i] << " " << t[color[i]] << endl;
	//}
	int ans = 1e18;
	for(int i = 1; i <= n; i++) ans = min(ans, s[color[i]]+t[color[i]]);
	cout << ans << endl;
	return;
}
signed main(){
	int T = read();
	while(T--){
		Solve();
	}
	return 0;
}

按理说是 $\mathcal{O}(n \log n)$ 的。