#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 2e5 + 5, M = 3e5 + 5, inf = 0x3f3f3f3f;
int cas, n, m, mat[N], chg[N], non[N];
vector <int> g[N];
namespace network {
    int s, t, tot, head[N], cur[N], dep[N];
    struct edge {
        int u, v, w, nxt;
    }e[M << 1];
    inline void add_edge (int u, int v, int w) {
        e[++tot] = {u, v, w, head[u]};
        head[u] = tot;
        e[++tot] = {v, u, w, head[v]};
        head[v] = tot;
    }
    bool bfs() {
        queue <int> q;
        for (int i = s; i <= t; i++) cur[i] = head[i], dep[i] = -1;
        dep[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = head[u]; i; i = e[i].nxt) {
                int v = e[i].v, w = e[i].w;
                if (w && dep[v] == -1) {
                    dep[v] = dep[u] + 1;
                    q.push(v);
                }
            }
        }
        return ~dep[t];
    }
    int dfs (int u, int flow) {
        if (!flow || u == t) return flow;
        int res = 0;
        for (int &i = cur[u]; i; i = e[i].nxt) {
            int v = e[i].v, w = e[i].w;
            if (w && dep[v] == dep[u] + 1) {
                int add_flow = dfs(v, min(flow, w));
                flow -= add_flow, res += add_flow;
                e[i].w -= add_flow, e[i ^ 1].w += add_flow;
            }
        }
        if (!res) dep[u] = -1;
        return res;
    }
    int Dinic() {
        int max_flow = 0;
        while (bfs()) max_flow += dfs(s, inf);
        return max_flow;
    }
}
using namespace network;
int dfs2 (int u);
int dfs1 (int u) {
    if (~non[u]) return non[u];
    if (!mat[u]) return non[u] = 1;
    non[u] = 0;
    if (dfs2(mat[u])) return non[u] = 1;
    return 0;
}
int dfs2 (int u) {
    if (~chg[u]) return chg[u];
    chg[u] = 0;
    for (int v : g[u]) {
        if (v != mat[u] && dfs1(v)) return chg[u] = 1;
    }
    return 0;
}
int main() {
    scanf ("%d", &cas);
    while (cas--) {
        scanf ("%d%d", &n, &m);
        s = 0, t = 2 * n + 1, tot = 1;
        for (int i = 1, u, v; i <= m; i++) {
            scanf ("%d%d", &u, &v);
            add_edge(u, v + n, 1);
            g[u].push_back(v + n);
            g[v + n].push_back(u);
        }
        for (int i = 1; i <= n; i++) {
            add_edge(s, i, 1);
            add_edge(i + n, t, 1);
        }
        Dinic();
        for (int i = 1; i <= m; i++) {
            if (!e[2 * i].w) {
                mat[e[2 * i].u] = e[2 * i].v;
                mat[e[2 * i].v] = e[2 * i].u;
            }
        }
        int cnt1 = 0, cnt2 = 0;
        for (int i = 1; i <= 2 * n; i++) chg[i] = non[i] = -1;
        for (int u = 1; u <= n; u++) cnt1 += dfs1(u);
        for (int u = 1; u <= n; u++) cnt2 += dfs1(u + n);
        printf ("%lld\n", 1ll * cnt1 * cnt2);
        for (int i = s; i <= t; i++) head[i] = 0;
        for (int i = 1; i <= 2 * n; i++) mat[i] = 0, g[i].clear();
    }
    return 0;
}