#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
# define im INT_MAX
# define umap unordered_map
# define uset unordered_set
# define f first
# define s second
# define pq priority_queue
# define pb push_back
# define ins insert
# define INF LLONG_MAX
#define int long long
uset<int> visited;
set<int> curr_component;
map<int,vector<int>> graph;
int component_num = 1;
void dfs(int node){
    visited.insert(node);
    curr_component.insert(node);
    for (int v : graph[node]){
        if (!visited.count(v)){dfs(v);}
    }
}

void setIO(string s) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

signed main(){
    // setIO("test");
    // ifstream cin("test.in");
    // ofstream cout("test.out");

    int t; cin >> t;
    while (t--){
        visited.clear(); graph.clear(); component_num=1;
        int n, m; cin >> n >> m;
        for (int i=0; i<m; i++){
            int a, b; cin >> a >> b;
            graph[a].pb(b); graph[b].pb(a);
        }

        vector<set<int>> components(n+1);
        set<int> component_with_1; set<int> component_with_n;
        for (int i=1; i<=n; i++){
            if (!visited.count(i)){
                curr_component.clear();
                dfs(i);
                components[component_num] = curr_component;
                component_num++;
            }
        }

        // print2dCont(components);

        vector<int> cost_from_1(n+1, LLONG_MAX); vector<int> cost_to_n(n+1, LLONG_MAX);
        for (int i=1; i<component_num; i++){
            if (components[i].count(1)){component_with_1 = components[i]; cost_from_1[i] = 0;}
            if (components[i].count(n)){component_with_n = components[i]; cost_to_n[i] = 0;}
        }

        // printArray(cost_from_1,component_num);
        // printArray(cost_to_n,component_num);

        // compute the min cost from component with 1 to all components and then from n to all components
        // then we take the min value of (1 to intermediary) + (intermediary to n)

        for (int id=1; id<component_num; id++){ // for all components except for 1
            set<int> intermediary = components[id];
            for (int mid_barn : intermediary){ // for all nodes in
                // compute minimum cost from mid_barn starting at start_barn
                auto it = component_with_1.lower_bound(mid_barn);
                if (it==begin(component_with_1)){
                    cost_from_1[id] = min(cost_from_1[id],(mid_barn-*it)*(mid_barn-*it));
                } else if (it==end(component_with_1)){
                    it--;
                    cost_from_1[id] = min(cost_from_1[id],(mid_barn-*it)*(mid_barn-*it));
                } else {
                    int cur = *it; --it;
                    int prev = *it;
                    cost_from_1[id] = min(cost_from_1[id],min((mid_barn-cur)*(mid_barn-cur),(mid_barn-prev)*(mid_barn-prev)));
                }
            }
        }
        // cout << "cost from component with 1:\n";
        // printMap(cost_from_1); cout << '\n';


        for (int id=1; id<component_num; id++){
            set<int> intermediary = components[id];
            for (int mid_barn : intermediary){
                // compute minimum cost from mid_barn starting at start_barn
                auto it = component_with_n.lower_bound(mid_barn);
                if (it==begin(component_with_n)){
                    cost_to_n[id] = min(cost_to_n[id],(mid_barn-*it)*(mid_barn-*it));
                } else if (it==end(component_with_n)){
                    it--;
                    cost_to_n[id] = min(cost_to_n[id],(mid_barn-*it)*(mid_barn-*it));
                } else {
                    int cur = *it; --it;
                    int prev = *it;
                    cost_to_n[id] = min(cost_to_n[id],min((mid_barn-cur)*(mid_barn-cur),(mid_barn-prev)*(mid_barn-prev)));
                }
            }
        }
        // cout << "cost from component with n:\n";
        // printMap(cost_to_n);

        int total_min_cost = LLONG_MAX;
        for (int id=1; id<component_num; id++){
            total_min_cost = min(total_min_cost,cost_from_1[id]+cost_to_n[id]);
        }
        cout << total_min_cost << '\n';
    }


    return 0;
}