1 #include <cstdio>  2 #include <algorithm>  3 #include <iostream>  4 #include <cstring>  5 #include <string>  6 #include <cmath>  7 #include <queue>  8 #include <vector>  9 #include <stack> 10 using namespace std; 11 #define N 20010 12 #define M 50010 13 struct node 14 { 15     int v, next, u; 16 }edge[M]; 17 int n, tot, cnt, num, head[N], dfn[N], low[N], belong[N], in[N], out[N]; 18 bool vis[N]; 19 stack<int> sta; 20  21 void init() 22 { 23     tot = 0; 24     num = 0; 25     cnt = 0; 26     while(!sta.empty()) sta.pop(); 27     memset(head, -1, sizeof(head)); 28     memset(vis, false, sizeof(vis)); 29     memset(low, 0, sizeof(low)); 30     memset(dfn, 0, sizeof(dfn)); 31     memset(belong, 0, sizeof(belong)); 32     memset(in, 0, sizeof(in)); 33     memset(out, 0, sizeof(out)); 34 } 35  36 void add(int u, int v) 37 { 38     edge[tot].next = head[u]; edge[tot].v = v; edge[tot].u = u; head[u] = tot++; 39 } 40  41 void tarjan(int u) 42 { 43     dfn[u] = low[u] = ++cnt; 44     sta.push(u); 45     vis[u] = true; 46     for(int i = head[u]; ~i; i = edge[i].next) { 47         int v = edge[i].v; 48         if(!dfn[v]) { 49             tarjan(v); 50             if(low[v] < low[u]) low[u] = low[v]; 51         } else { 52             if(vis[v] && low[u] > dfn[v]) low[u] = dfn[v]; 53         } 54     } 55     if(dfn[u] == low[u]) { 56         num++; 57         int top = 0; 58         while(top != u) { 59             top = sta.top(); 60             belong[top] = num; 61             vis[top] = 0; 62             sta.pop(); 63         } 64     } 65 } 66  67 int main() 68 { 69     int t; 70     scanf("%d", &t); 71     while(t--) { 72         init(); 73         int m; 74         scanf("%d%d", &n, &m); 75         for(int i = 0; i < m; i++) { 76             int u, v; 77             scanf("%d%d", &u, &v); 78             add(u, v); 79         } 80         for(int i = 1; i <= n; i++) { 81             if(!dfn[i]) { 82                 tarjan(i); 83             } 84         } 85         for(int u = 1; u <= n; u++) { 86             for(int i = head[u]; ~i; i = edge[i].next) { 87                 int v = edge[i].v; 88                 if(belong[u] != belong[v]) { 89                     in[belong[u]]++; 90                     out[belong[v]]++; 91                 } 92             } 93         } 94         int inn = 0, outt = 0; 95         for(int i = 1; i <= num; i++) { 96             if(in[i] == 0) inn++; 97             if(out[i] == 0) outt++; 98         } 99         int ans = max(inn, outt);100         if(num == 1) ans = 0;101         printf("%d\n", ans);102     }103     return 0;104 }