#include "bits/stdc++.h"
#define int long long
#define ull unsigned long long
#define double long double
#define PII pair<int,int>
#define TIII tuple<int,int,int>
#define LL __int128
#define eps 1e-6
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 4e5 + 10, M = 2e6 + 10, mod = 1e9 + 7, inf = 1e18;
//HLPP算法求最大流O(n*n*sqrt(m))
int n, m, S, T;
int h[N], w[M], ne[M], to[M], idx;
int depth[N], gap[N];
int E[N];//每个节点的超额量
struct cmp
{
    bool operator()(int a, int b) const
    {
        return depth[a] < depth[b];
    }
};
priority_queue<int, vector<int>, cmp> heap;
bool st[N];
int cnt;

void add(int a, int b, int c)
{
    to[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    to[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

void bfs()
{
    for (int i = 0; i <= cnt; i++) depth[i] = -1;
    depth[T] = 0;
    queue<int> q;
    q.push(T);
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = h[u]; ~i; i = ne[i])
        {
            int v = to[i], val = w[i ^ 1];
            if (val && depth[v] == -1)
            {
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }
}

void push(int u)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int v = to[i], val = w[i];
        if (val && depth[v] + 1 == depth[u])
        {
            int flow = min(E[u], val);
            w[i] -= flow;
            w[i ^ 1] += flow;
            E[u] -= flow;
            E[v] += flow;
            if (v != S && v != T && !st[v])
            {
                heap.push(v);
                st[v] = true;
            }
            if (E[u] == 0) break;
        }
    }
}

void update(int u)
{
    depth[u] = inf;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int v = to[i], val = w[i];
        if (val && depth[v] + 1 < depth[u])
        {
            depth[u] = depth[v] + 1;
        }
    }
}

int HLPP()
{
    bfs();
    depth[S] = cnt; //将源点的高度设置为n
    for (int i = 0; i <= cnt; i++)
    {
        if (~depth[i]) gap[depth[i]]++;
    }
    //将于源点直接相连的点满额推送
    for (int i = h[S]; ~i; i = ne[i])
    {
        int v = to[i], val = w[i];
        int flow = w[i];
        if (flow)
        {
            w[i] -= flow;
            w[i ^ 1] += flow;
            E[S] -= flow;
            E[v] += flow;
            if (v != S && v != T && !st[v])
            {
                heap.push(v);
                st[v] = true;
            }
        }
    }
    while (heap.size())
    {
        int u = heap.top();
        heap.pop();
        st[u] = false;
        //推送流量
        push(u);
        //如果还有超额量 说明depth[u]的高度不够
        if (E[u])
        {
            //gap优化 将高度大于depth[u]且小于n+1的点的高度修改为n+1,以便快速推送给S
            //因为当前节点是最高的所以修改的节点一定不在优先队列中，不必担心修改对优先队列会造成影响
            if (--gap[depth[u]] == 0)
            {
                for (int i = 0; i <= cnt; i++)
                {
                    if (i != S && i != T && depth[i] > depth[u] && depth[i] < cnt + 1)
                    {
                        depth[i] = cnt + 1;
                    }
                }
            }
            //找到有流量而且边的另一端v高度最小的边，将depth[u]设置为depth[v]+1
            update(u);
            gap[depth[u]]++;
            heap.push(u);
            st[u] = true;
        }
    }
    return E[T];
}

void solve()
{
    cin >> n >> m;
    S = 0, T = cnt = n + n + 1;
    for (int i = 0; i <= cnt; i++) h[i] = -1;
    for (int i = 1; i <= n; i++)
    {
        add(S, i, 1), add(i + n, T, 1);
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v + n, 1);
    }
    HLPP();
    //    cout << HLPP() << endl;
    //增加原图的最大匹配 即让残留网络的 S T 变得连通 在残留网络中遍历S能到达的点  T能够到达的点
    vector<int> vis(cnt + 1);
    int cnt1 = 0, cnt2 = 0;
    function<void(int, int)> dfs = [&](int u, int id)
    {
        if (id == S) cnt1 += (u <= n);
        else
        {
            cnt2 += (u > n);
        }
        vis[u] = true;
        for (int i = h[u]; ~i; i = ne[i])
        {
            int v = to[i], cap = w[i];
            if (vis[v]) continue;
            //在残留网络中遍历 从 S 出发即未经过 即cap == 1, 从 T 出发未经过 cap == 0
            if ((id == S && cap != 1) || (id == T && cap != 0)) continue;
            dfs(v, id);
        }
    };
    dfs(S, S), dfs(T, T);
    cout << (cnt1 - 1) * (cnt2 - 1) << endl;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(2);

#ifndef ONLINE_JUDGE
    freopen("in.txt", "rt", stdin);
    freopen("out.txt", "wt", stdout);
#endif

    int Cases = 1;
    cin >> Cases;
    while (Cases--)
    {
        solve();
    }
    return 0;
}