#include <algorithm> #include <cstdio> #include <numeric> #include <queue> #include <unordered_map> #include <vector> using namespace std; using i64 = long long; struct Solution { int n; vector<bool> vis, cover; vector<int> ans, in; unordered_map<int, vector<int>> graph; void connect(int u, int v) { graph[u].emplace_back(v); ++in[v]; } void solve() { queue<int> nodes; auto bfs = [&nodes, this](int start) { while (!nodes.empty()) { int u = nodes.front(); nodes.pop(); vis[u] = true; for (auto v : graph[u]) { if (v != start) ans[v] = 2; if (--in[v] == 0 && !vis[v]) nodes.emplace(v); } } }; for (const auto& node : graph) { int i = node.first; if (in[i] == 0 && !vis[i]) { nodes.emplace(i); ans[i] = max(ans[i], 1); bfs(i); } } for (const auto& node : graph) { int i = node.first; if (cover[i] && !vis[i]) { nodes.emplace(i); ans[i] = max(ans[i], 1); bfs(i); } } for (const auto& node : graph) { int i = node.first; if (!vis[i]) { nodes.emplace(i); ans[i] = max(ans[i], 1); bfs(i); } } } void main() { int m, i; scanf("%d %d", &n, &m); vector<int> x(m), c(m), y(m), d(m), idx(m); cover.resize(n); ans.resize(n); vis.resize(n); in.resize(n); for (i = 0; i < m; ++i) { scanf("%d %d %d %d", &x[i], &c[i], &y[i], &d[i]); idx[i] = i; --x[i]; --y[i]; } sort(idx.begin(), idx.end(), [&c, &d](int i, int j) { return c[i] + d[i] < c[j] + d[j]; }); for (i = m - 1; i >= 0; --i) { if (c[idx[i]] == 2 && d[idx[i]] == 2) cover[x[idx[i]]] = cover[y[idx[i]]] = true; else break; } for (i = 0; i < m; ++i) { if (c[idx[i]] == 1 && d[idx[i]] == 1) ans[x[idx[i]]] = ans[y[idx[i]]] = 1; else if (c[idx[i]] == 1 && d[idx[i]] == 2) connect(x[idx[i]], y[idx[i]]); else if (c[idx[i]] == 2 && d[idx[i]] == 1) connect(y[idx[i]], x[idx[i]]); else break; } solve(); for (; i < m; ++i) ans[x[idx[i]]] = ans[y[idx[i]]] = 2; printf("%d\n", accumulate(ans.begin(), ans.end(), 0)); } }; int main() { int t; scanf("%d", &t); while (t-- > 0) Solution().main(); return 0; }