#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

const int MaxN = 1e5 + 10;

set<long long> s[MaxN];
int fa[MaxN], n, m, t;
long long dis[2][MaxN], ans;

void Merge(int x, int y) {
  x = fa[x], y = fa[y];
  if (x == y) {
    return;
  }
  if (s[x].size() > s[y].size()) {
    swap(x, y);
  }
  for (int i : s[x]) {
    s[y].insert(i);
    fa[i] = y;
  }
  set<long long>().swap(s[x]);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> t; t; t--) {
    cin >> n >> m, ans = 1e9;
    for (int i = 1; i <= n; i++) {
      set<long long>().swap(s[i]);
      s[i].insert(i), fa[i] = i;
    }
    for (int i = 1, u, v; i <= m; i++) {
      cin >> u >> v;
      Merge(u, v);
    }
    for (int i = 2; i <= n; i++) {
      auto tmp1 = s[fa[1]].lower_bound(i), tmp2 = s[fa[1]].upper_bound(i);
      if (tmp2 != s[fa[1]].begin()) {
        tmp2--;
      }
      dis[0][i] = min((*tmp1 - i) * (*tmp1 - i), (*tmp2 - i) * (*tmp2 - i));
    }
    for (int i = 1; i < n; i++) {
      auto tmp1 = s[fa[n]].lower_bound(i), tmp2 = s[fa[n]].upper_bound(i);
      if (tmp2 != s[fa[n]].begin()) {
        tmp2--;
      }
      dis[1][i] = min((*tmp1 - i) * (*tmp1 - i), (*tmp2 - i) * (*tmp2 - i));
    }
    dis[0][1] = dis[1][n] = 1e18;
    for (int i = 1; i <= n; i++) {
      ans = min(ans, dis[0][i] + dis[1][i]);
    }
    cout << ans << endl;
  }
  return 0;
}