#include<bits/stdc++.h>

#define int long long
using i64 = long long;
constexpr i64 INF = 1e18;
struct Edge {
    int y;
    i64 w;
};
std::vector<int> v[200005];
std::vector<Edge> e;
std::vector<int> cur, lv, gap;
int n, s, t;

void bfs() {//分层
    for (int i = 1; i <= n; i++)lv[i] = -1;
    lv[t] = 0;
    gap[0] = 1;
    std::queue<int> q;
    q.push(t);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i: v[x]) {
            int y = e[i].y;
            if (lv[y] == -1) {
                lv[y] = lv[x] + 1;
                gap[lv[y]]++;
                q.push(y);
            }
        }
    }
}

i64 dfs(int x = s, i64 flow = INF) {
    if (x == t)return flow;
    i64 rmn = flow; // 剩余的流量
    for (int i = cur[x]; i < v[x].size() && rmn > 0; i++) // 如果已经没有剩余流量则退出
    {
        cur[x] = i; // 当前弧优化，更新当前弧
        int y = e[v[x][i]].y;
        i64 w = e[v[x][i]].w;
        if (w > 0 && lv[y] == lv[x] - 1) // 往层数低的方向增广
        {
            i64 c = dfs(y, std::min(w, rmn)); // 尽可能多地传递流量
            rmn -= c; // 剩余流量减少
            e[v[x][i]].w -= c; // 更新残余容量
            e[v[x][i] ^ 1].w += c;
        }
    }
    if (rmn > 0) {//GAP
        gap[lv[x]]--;
        if (gap[lv[x]] == 0)lv[s] = n + 1;
        lv[x]++;
        gap[lv[x]]++;
    }
    return flow - rmn; // 返回传递出去的流量的大小
}

i64 MaxFlow() {
    bfs();
    i64 ans = 0;
    if (lv[s] == -1)return 0;
    while (lv[s] <= n) {
        for (int i = 1; i <= n; i++)cur[i] = 0;
        ans += dfs();
    }
    return ans;
}

void solve() {
    int m;
    std::cin >> n >> m;
    s = n * 2 + 1;
    t = n * 2 + 2;
    for (int i = 1; i <= n * 2 + 2; i++)v[i].clear();
    cur.assign(n * 2 + 5, 0);
    lv.assign(n * 2 + 5, 0);
    gap.assign(n * 2 + 5, 0);
    e.clear();
    auto AddEdge = [&](int x, int y, i64 w) -> void {
        e.emplace_back(x, 0);
        v[y].push_back((int) e.size() - 1);
        e.emplace_back(y, w);
        v[x].push_back((int) e.size() - 1);
    };
    for (int i = 1; i <= m; i++) {
        int x, y;
        std::cin >> x >> y;
        AddEdge(x, y + n, 1);
    }
    for (int i = 1; i <= n; i++) {
        AddEdge(s, i, 1);
        AddEdge(i + n, t, 1);
    }
    std::vector<bool> vis(n * 2 + 5);
    i64 suma = 0, sumb = 0;
    auto dfs1 = [&](auto &&self, int x) -> void {
        if (x <= n)suma++;
        for (int i: v[x]) {
            int y = e[i].y;
            i64 w = e[i].w;
            if (vis[y])continue;
            if (w > 0) {
                vis[y] = true;
                self(self, y);
            }
        }
    };
    auto dfs2 = [&](auto &&self, int x) -> void {
        if (x > n && x <= 2 * n)sumb++;
        for (int i: v[x]) {
            int y = e[i].y;
            i64 w = e[i].w;
            if (vis[y])continue;
            if (w == 0) {
                vis[y] = true;
                self(self, y);
            }
        }
    };
    n = n * 2 + 2;
    MaxFlow();
    n = (n - 2) / 2;
    vis[s] = true;
    vis[t] = true;
    dfs1(dfs1, s);
    vis.assign(n * 2 + 5, false);
    vis[s] = true;
    vis[t] = true;
    dfs2(dfs2, t);
    std::cout << suma * sumb << '\n';
}

signed main() {
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
    int T;
    std::cin >> T;
    while (T--)solve();
}

In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/c++allocator.h:33,
                 from /usr/include/c++/13/bits/allocator.h:46,
                 from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:1:
/usr/include/c++/13/bits/new_allocator.h: In instantiation of ‘void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = Edge; _Args = {long long int&, int}; _Tp = Edge]’:
/usr/include/c++/13/bits/alloc_traits.h:537:17:   required from ‘static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = Edge; _Args = {long long int&, int}; _Tp = Edge; allocator_type = std::allocator<Edge>]’
/usr/include/c++/13/bits/vector.tcc:117:30:   required from ‘std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {long long int&, int}; _Tp = Edge; _Alloc = std::allocator<Edge>; reference = Edge&]’
answer.code:82:23:   required from here
/usr/include/c++/13/bits/new_allocator.h:187:11: error: new initializer expression list treated as compound expression [-fpermissive]
  187 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/new_allocator.h:187:11: error: no matching function for call to ‘Edge::Edge(int)’
answer.code:6:8: note: candidate: ‘Edge::Edge()’
    6 | struct Edge {
      |        ^~~~
answer.code:6:8: note:   candidate expects 0 arguments, 1 provided
answer.code:6:8: note: candidate: ‘constexpr Edge::Edge(const Edge&)’
answer.code:6:8: note:   no known conversion for argument 1 from ‘int’ to ‘const Edge&’
answer.code:6:8: note: candidate: ‘constexpr Edge::Edge(Edge&&)’
answer.code:6:8: note:   no known conversion for argument 1 from ‘int’ to ‘Edge&&’
/usr/include/c++/13/bits/new_allocator.h: In instantiation of ‘void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = Edge; _Args = {long long int&, long long int&}; _Tp = Edge]’:
/usr/include/c++/13/bits/alloc_traits.h:537:17:   required from ‘static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = Edge; _Args = {long long int&, long long int&}; _Tp = Edge; allocator_type = std::allocator<Edge>]’
/usr/include/c++/13/bits/vector.tcc:117:30:   required from ‘std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {long long int&, long long int&}; _Tp = Edge; _Alloc = std::allocator<Edge>; reference = Edge&]’
answer.code:84:23:   required from here
/usr/include/c++/13/bits/new_allocator.h:187:11: error: new initializer expression list treated as compound expression [-fpermissive]
  187 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/new_allocator.h:187:11: error: no matching function for call to ‘Edge::Edge(long long int&)’
answer.code:6:8: note: candidate: ‘Edge::Edge()’
    6 | struct Edge {
      |        ^~~~
answer.code:6:8: note:   candidate expects 0 arguments, 1 provided
answer.code:6:8: note: candidate: ‘constexpr Edge::Edge(const Edge&)’
answer.code:6:8: note:   no known conversion for argument 1 from ‘long long int’ to ‘const Edge&’
answer.code:6:8: note: candidate: ‘constexpr Edge::Edge(Edge&&)’
answer.code:6:8: note:   no known conversion for argument 1 from ‘long long int’ to ‘Edge&&’