#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define sz(s) (int)(s).size()
#define all(s) s.begin(),s.end()

void Speed() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

void solve() {
    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
    }
    if(m < n - 1 || m > 1ll * n * (n - 1) / 2) return cout << "-1\n", void();
    ll ans = 0;
    for(int i = 2; i <= n; i++) ans += i + 1;
    int nxt = 2;
    for(int j = n - 1, a = nxt, c = 5; j < m; j++){
        if(c - a <= a){
            c++;
            while(c - nxt > n) nxt++;
            a = nxt;
            assert(c - a > a);
        }
        ans += c; a++;
    }
    cout << ans << '\n';
}

int main() {
    Speed();
    int tc = 1;
    cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}