#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair <int, int> pii;
typedef long long LL;

inline int read() {
    int x = 0, f = 0;
    char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
    while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f? -x : x;
}
template<class T>
struct Flow {
    const int n;
    struct Edge {
        int to;
        T cap;
        Edge(int to, T cap) : to(to), cap(cap) {}
    };
    std::vector<Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> cur, h;
    Flow(int n) : n(n), g(n) {}
    
    bool bfs(int s, int t) {
        h.assign(n, -1);
        std::queue<int> que;
        h[s] = 0;
        que.push(s);
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            for (int i : g[u]) {
                auto [v, c] = e[i];
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    if (v == t) {
                        return true;
                    }
                    que.push(v);
                }
            }
        }
        return false;
    }
    
    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        auto r = f;
        for (int &i = cur[u]; i < int(g[u].size()); ++i) {
            const int j = g[u][i];
            auto [v, c] = e[j];
            if (c > 0 && h[v] == h[u] + 1) {
                auto a = dfs(v, t, std::min(r, c));
                e[j].cap -= a;
                e[j ^ 1].cap += a;
                r -= a;
                if (r == 0) {
                    return f;
                }
            }
        }
        return f - r;
    }
    int addEdge(int u, int v, T c) {
        int id;
        g[u].push_back(e.size());
        id = e.size();
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
        return id;
    }
    T maxFlow(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, std::numeric_limits<T>::max());
        }
        return ans;
    }
};
//Flow<int> flow(2 * n + 2);

const int MAXN = 2e5;
struct edge {
    int x, y, id;
}e[MAXN + 10];

vector <int> G[MAXN + 10][2];

int vis[MAXN + 10], ok[MAXN + 10][2];
int dfs(int x, int op) {
    int res = 0;
    while (G[x][op].size()) {
        int v = G[x][op].back(); G[x][op].pop_back();
        if (!vis[v]) {
            assert(op == 1);
            return ok[x][op] = 1;
        }
        if (ok[v][op ^ 1] != -1)
            res |= ok[v][op ^ 1];
        res |= dfs(v, op ^ 1);
    }
    return ok[x][op] = res;
}
int main() {
    int T = read();
    while (T--) {
        int n, m;
        n = read(), m = read();
        Flow<int> flow(n + n + 4);
        int s = n + n + 1, t = n + n + 2;
        for (int i = 1; i <= n; ++i) flow.addEdge(s, i, 1);
        for (int i = 1; i <= m; ++i) flow.addEdge(i + n, t, 1);
        for (int i = 1; i <= m; ++i) {
            int x = read(), y = read();
            e[i].x = x, e[i].y = y;
            e[i].id = flow.addEdge(x, y + n, 1);
        }
        int match = flow.maxFlow(s, t);
        //cerr << match << endl;
        for (int i = 1; i <= m; ++i) {
            int op = flow.e[e[i].id].cap;
            if (!op)
                vis[e[i].x] = vis[e[i].y + n] = 1;
            G[e[i].x][op].pb(e[i].y + n);
            G[e[i].y + n][op].pb(e[i].x);
        }
        for (int i = 1; i <= n + n; ++i) ok[i][0] = ok[i][1] = -1;
        for (int i = 1; i <= n + n; ++i) {
            for (int j = 0; j <= 1; ++j)
                if (ok[i][j] == -1) dfs(i, j);
        }
        int c1 = 0, c2 = 0;
        for (int i = 1; i <= n; ++i)
            if (!vis[i] || ok[i][0]) ++c1;
        for (int i = 1; i <= n; ++i)
            if (!vis[n + i] || ok[n + i][0]) ++c2;
    //    cerr << c1 << " " << c2 << endl;
        LL ans = 0;
        ans = 1ll * (n - match) * c2 + 1ll * (n - match) * c1;
        ans -= 1ll * (n - match) * (n - match);
        printf("%lld\n", ans);
        for (int i = 1; i <= n + n; ++i) {
            vis[i] = 0;
            G[i][0].clear(), G[i][1].clear();
        }
    }
    return 0;
}