#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], cp[MAXN + 10][2];

int vis[MAXN + 10], ok[MAXN + 10][2];
int dfs(int x, int op) {
	int& res = ok[x][op];
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];
		else {
			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 <= n; ++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)
				cp[i][j] = G[i][j];
		for (int i = 1; i <= n; ++i)
			if (ok[i][0] == -1) dfs(i, 0);
		for (int i = 1; i <= n + n; ++i) 
			for (int j = 0; j <= 1; ++j)
				G[i][j] = cp[i][j];
		for (int i = 1; i <= n; ++i)
			if (ok[i + n][0] == -1) dfs(i + n, 0);
		int c1 = 0, c2 = 0;
		int rnm1 = 0, rnm2 = 0;
		for (int i = 1; i <= n; ++i) {
			if (!vis[i] || ok[i][0]) ++c1;
			if (ok[i][0] && vis[i]) ++rnm1;
		}
		for (int i = 1; i <= n; ++i) {
			if (!vis[n + i] || ok[n + i][0]) ++c2;
			if (vis[n + i] && ok[n + i][0]) ++rnm2;
		}
	//	cerr << c1 << " " << c2 << endl;
		LL ans = 0;
		ans = 1ll * (n - match) * c2 + 1ll * (n - match) * c1;
		ans -= 1ll * (n - match) * (n - match);
		ans += 1ll * rnm1 * rnm2;
		printf("%lld\n", ans);
		for (int i = 1; i <= n + n; ++i) {
			vis[i] = 0;
			G[i][0].clear(), G[i][1].clear();
			cp[i][0].clear(); cp[i][1].clear();
		}
	}
	return 0;
}