/// USACO 2021 December Contest, Silver - Connecting Two Barns
/// https://u...content-available-to-author-only...o.org/index.php?page=viewproblem2&cpid=1159
/// Author: Qwerty
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
int n, m;
vector<int> a[MAXN];
int vis[MAXN];
vector<int> comp[MAXN];
int cnt = 1;
int g1, gn;
void dfs(int u){
    if (u == 1) g1 = cnt;
    if (u == n) gn = cnt;
    vis[u] = 1;
    comp[cnt].push_back(u);
    for (int v: a[u]){
         if (vis[v] == 0){
             dfs(v);
         }
    }
}
long long cal(int u, int v){
    long long dist = 1e18;
    for (int x: comp[v]){
         int index = lower_bound(comp[u].begin(), comp[u].end(), x) - comp[u].begin();
         if (index != 0) dist = min(dist, 1LL * abs(comp[u][index - 1] - x));
         if (index != comp[u].size()) dist = min(dist, 1LL * abs(comp[u][index] - x));
    }
    return dist * dist;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--){
        cnt = 1;
        cin >> n >> m;
        for (int i = 1; i <= m; i++){
             int x, y;
             cin >> x >> y;
             a[x].push_back(y);
             a[y].push_back(x);
        }
        long long ans = 1e18;
        for (int i = 1; i <= n; i++){
             if (vis[i] == 0){
                 dfs(i);
                 cnt++;
             }
        }
        cnt--;
        sort(comp[g1].begin(), comp[g1].end());
        sort(comp[gn].begin(), comp[gn].end());
        for (int i = 1; i <= cnt; i++){
             ans = min(ans, cal(g1, i) + cal(gn, i));
        }
        cout << ans << '\n';
        for (int i = 1; i <= n; i++) {
             a[i].clear();
             vis[i] = 0;
             comp[i].clear();
        }
    }
}