#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <climits>

#define int long long
using namespace std;

#define all(c) c.begin(), c.end()
#define line "\n"

typedef vector<int> vi;
typedef vector<vector<int>> vvi;

vvi graph, dsu;
vector<bool> vis;
vi travel;

void dfs(int node) {
    if (vis[node]) return;
    vis[node] = true;
    travel.push_back(node);
    for (int adj : graph[node]) dfs(adj);
}

void solve() {
    int n, m; cin >> n >> m;

    graph.assign(n + 1, vector<int>());
    vis.assign(n + 1, false);
    dsu.clear();

    for (int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    travel.clear();
    dfs(1);
    sort(all(travel));
    vi dsu1 = travel;

    travel.clear();
    dfs(n);
    sort(all(travel));
    vi dsun = travel;

    for (int i = 2; i < n; i++) {
        if (!vis[i]) {
            travel.clear();
            dfs(i);
            dsu.push_back(travel);
        }
    }

    int ans = LLONG_MAX;
    for (int x : dsu1) {
        auto it = upper_bound(all(dsun), x);
        if (it != dsun.end()) ans = min(ans, (*it) * (*it));
        if (it != dsun.begin()) {
            --it;
            ans = min(ans, (*it) * (*it));
        }
    }

    for (auto &v : dsu) {
        for (int x : v) {
            int val1 = LLONG_MAX, val2 = LLONG_MAX;
            auto it = upper_bound(all(dsun), x);
            if (it != dsun.end()) val1 = min(val1, (*it - x) * (*it - x));
            if (it != dsun.begin()) {
                --it;
                val1 = min(val1, (*it - x) * (*it - x));
            }
            it = upper_bound(all(dsu1), x);
            if (it != dsu1.end()) val2 = min(val2, (*it - x) * (*it - x));
            if (it != dsu1.begin()) {
                --it;
                val2 = min(val2, (*it - x) * (*it - x));
            }
            ans = min(ans, val1 + val2);
        }
    }

    if (dsu1 == dsun) cout << 0 << line;
    else cout << ans << line;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t; cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}