• + 0 comments
    #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;
        
        }
    }