#define AK return
#define USACO 0;
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int T;
int n , m;
int ufs[N];
int c1[N] , cn[N] , ct1 = 0 , ctn = 0;
ll ans = 0x3f3f3f3f , f[N] , g[N];

int find( int x ){
    if( x == ufs[x] ) return x;
    else return ufs[x] = find(ufs[x]);
}

void unite( int x , int y ){
    if( find(x) != find(y) ){
        ufs[find(x)] = find(y);
    }
}

ll dis( int x , int y ){
    return (ll)(x-y)*(x-y);
}

void solve( ){
    memset( f , 0x7f , sizeof( f ) );
    memset( g , 0x7f , sizeof( g ) );
    f[find(1)] = 0;
    g[find(n)] = 0;
    for( int i = 1 ; i <= n ; i++ ){
        int u = find(i);
        if( u != find( 1 ) ){
            int it = upper_bound( c1 + 1 , c1 + ct1 + 1 , i ) - c1;
            f[u] = min( f[u] , (ll)( dis( c1[it] , i ) ) );
            if( it > ct1 ) f[u] = min( f[u] , (ll)(dis( c1[it-1] , i ) ) );
        }
        if( u != find( n ) ){
            int it = upper_bound( cn + 1 , cn + ctn + 1 , i ) - cn;
            g[u] = min( g[u] , (ll)( dis( cn[it] , i ) ) );
            if( it > 1 ) g[u] = min( g[u] , (ll)(dis( cn[it-1] , i ) ) );
        }
    }
}

int main( ) {
    cin >> T;
    while( T-- ){
        cin >> n >> m;
        for( int i = 1 ; i <= n ; i++ ) ufs[i] = i;
        memset( c1 , 0 , sizeof(c1) );
        memset( cn , 0 , sizeof(cn) );
        ct1 = 0; ctn = 0;
        for( int i = 1 , u , v ; i <= m ; i++ ){
            cin >> u >> v;
            unite( u , v );
        }
        /*if( find(1) == find(n) ){
            cout << 0 <<endl;
            continue;
        }*/
        for( int i = 1 ; i <= n ; i++ ){
            if( find(i) == find(1) ){
                c1[++ct1] = i;
            }
            else if( find(i) == find(n) ){
                cn[++ctn] = i;
            }
        }
        sort( c1 + 1 , c1 + ct1 + 1 );
        sort( cn + 1 , cn + ctn + 1 );
        solve( );
        ans = (ll)(n-1ll)*(n-1ll);
        for( int i = 1 ; i <= n ; i++ ){
            ans = min( ans , (f[find(i)]+g[find(i)]) );
        }
        cout << ans <<endl;
    }
    AK USACO
}