#include <bits/stdc++.h>
#define ll unsigned long long int
#define MAX 10e5+5
using namespace std;
vector<int> parent(MAX);
vector<int> no_of_friends(MAX);

ll findparent(int x)
{
    if(parent[x] == x) 
        return x;
    return parent[x] = findparent(parent[x]);
}

ll value(ll n){
    ll t1=n*(n+1)*(2*n+1);
    t1/=6;
    ll t2=n*(n+1);
    t2/=2;
    return t1-t2;
}

int main()
{
    int q;
    cin>>q;
    while(q--)
    {
        ll n,m;
        cin>>n>>m;
        ll Total = 0;
        ll current = 0;
        ll ans = 0;
        for(ll i=1;i<=n;i++)
        {
            parent[i] = i;
            no_of_friends[i] = 1;
        }
        for(ll i=0;i<m;i++)
        {
            ll u,v;
            cin>>u>>v;
            
            ll pu = findparent(u);
            ll pv = findparent(v);
            
            if(pu != pv)
            {
                parent[pv] = pu ;
                no_of_friends[pu] += no_of_friends[pv];
            }
        }
        vector<ll> p;
        for(ll i = 1 ; i <= n ; i++ ){
            if(parent[i] == i)
                p.push_back(no_of_friends[i]);
                
        }
        sort(p.begin(),p.end(),greater<ll>());
        for(ll i = 0 ; i<p.size() ;i++) 
        {
            //cout<<p[i]<<endl;
            current+=(p[i]-1);
            ans +=value(p[i])+Total*(p[i]-1);
            //cout<<ans<<endl;
            Total+=(p[i] * (p[i]-1));
        }
       // cout<<m<<" "<<Total<<endl;
        ans+=((m-current)*Total);
        cout<<ans<<endl;
    
    }
}

parent={}
no_of_friends={}

def findparent(x):
    if parent[x] == x:
        return x
    parent[x] = findparent(parent[x])
    return parent[x]

def value (n):
    t1=n*(n+1)*(2*n+1)
    t1/=6
    t2=n*(n+1)
    t2/=2
    return t1-t2

    
def valueOfFriendsship(n,m, friendships):
    # Write your code here
    total, current, ans =0,0,0
    for i in range(1,n+1):
        parent[i] = i
        no_of_friends[i] = 1
    for i in range(m):
        u,v=friendships[i][0],friendships[i][1]
        pu,pv = findparent(u),findparent(v)
        if pu != pv:
                parent[pv] = pu
                no_of_friends[pu] += no_of_friends[pv]              
    p=[]
    for i in range(1,n+1):
        if(parent[i] == i):
            p.append(no_of_friends[i])
    p.sort(reverse=True)
    for i in range(len(p)):
        current+=(p[i]-1)
        ans +=value(p[i])+total*(p[i]-1)
        total+=(p[i] * (p[i]-1))
    ans+=((m-current)*total)
    return int(ans)