1 /**************************************************
  2  * Author     : xiaohao Z
  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
  4  * Last modified : 2014-01-30 22:43
  5  * Filename     : uva_11324.cpp
  6  * Description     : 
  7  * ************************************************/
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <cmath>
 14 #include <algorithm>
 15 #include <queue>
 16 #include <stack>
 17 #include <vector>
 18 #include <set>
 19 #include <map>
 20 #define MP(a, b) make_pair(a, b)
 21 #define PB(a) push_back(a)
 22 
 23 using namespace std;
 24 typedef long long ll;
 25 typedef pair<int, int> pii;
 26 typedef pair<unsigned int,unsigned int> puu;
 27 typedef pair<int, double> pid;
 28 typedef pair<ll, int> pli;
 29 typedef pair<int, ll> pil;
 30 
 31 const int INF = 0x3f3f3f3f;
 32 const double eps = 1E-6;
 33 const int LEN = 1010;
 34 vector<int> Map[LEN];
 35 int n, m, dclock, scc_cnt, dp[LEN];
 36 int  dfn[LEN], sccn[LEN], low[LEN], cnt[LEN], tMap[LEN][LEN];
 37 stack<int> s;
 38 
 39 void sccinit()
 40 {
 41      for(int i=0; i<LEN; i++) Map[i].clear();
 42      while(!s.empty()) s.pop();
 43      memset(dfn, 0, sizeof dfn);
 44      memset(sccn, 0, sizeof sccn);
 45      dclock = scc_cnt = 0;
 46 }
 47 
 48 void dfs(int u){
 49     low[u] = dfn[u] = ++dclock;
 50     s.push(u);
 51     for(int i=0; i<Map[u].size(); i++){
 52         int v = Map[u][i];
 53         if(!dfn[v]){
 54              dfs(v);
 55              low[u] = min(low[u], low[v]);
 56         }else if(!sccn[v]) low[u] = min(low[u], dfn[v]);
 57     }
 58     if(low[u] == dfn[u]){
 59          scc_cnt++;
 60          while(1){
 61             int x = s.top();s.pop();
 62             sccn[x] = scc_cnt;
 63             if(x == u) break;
 64          }
 65     }
 66 }
 67 
 68 int getans(int v){
 69     if(dp[v]!=-1) return dp[v];
 70     int ret = cnt[v];
 71     for(int i=1; i<=scc_cnt; i++) 
 72         if(tMap[v][i])ret = max(ret, cnt[v]+getans(i));
 73     return dp[v] = ret;
 74 }
 75 
 76 int main()
 77 {
 78 //    freopen("in.txt", "r", stdin);
 79     
 80     int a, b, T;
 81     scanf("%d", &T);
 82     while(T--){
 83         sccinit();
 84         scanf("%d%d", &n, &m);
 85         for(int i=0; i<m; i++){
 86             scanf("%d%d", &a, &b);
 87             Map[a].PB(b);
 88         }
 89         for(int i=1; i<=n; i++)if(!dfn[i])dfs(i);
 90         memset(cnt, 0, sizeof cnt);
 91         memset(tMap, 0, sizeof tMap);
 92         memset(dp, -1, sizeof dp);
 93         for(int i=1; i<=n; i++){
 94             for(int j=0; j<Map[i].size(); j++){
 95                 if(sccn[i] == sccn[Map[i][j]]) continue;
 96                 tMap[sccn[i]][sccn[Map[i][j]]] = 1;
 97             }
 98         }
 99         int ans = 0;
100         for(int i=1; i<=n; i++) cnt[sccn[i]] ++;
101         for(int i=scc_cnt; i>0; i--)if(dp[i] < 0)getans(i);
102         for(int i=scc_cnt; i>0; i--) ans = max(ans, dp[i]);
103         printf("%d\n", ans);
104     }
105     return 0;
106 }