#include <bits/stdc++.h>

 #define LL long long

 #define pii pair<int,int>

 using namespace std;

 const int N=+;

 const int INF=0x7f7f7f7f;

 vector<int> vect[N];

 stack<int> stac;

 bool chu[N], ru[N];

 int scc_no[N], lowlink[N], dfn[N];

 int dfn_clock, scc_cnt;

 int n, m;

 void DFS(int x)

 {

     stac.push(x);

     dfn[x]=lowlink[x]=++dfn_clock;

     for(int i=; i<vect[x].size(); i++)

     {

         int t=vect[x][i];

         if(!dfn[t])

         {

             DFS(t);

             lowlink[x]=min(lowlink[x],lowlink[t]);

         }

         else if(!scc_no[t]) //如果t不属于任何一个强连通分量

             lowlink[x]=min(lowlink[x],dfn[t]);

     }

     if(lowlink[x]==dfn[x])

     {

         scc_cnt++;

         while(true)

         {

             int t=stac.top();

             stac.pop();

             scc_no[t]=scc_cnt;

             if(t==x)    break;

         }

     }

 }

 int cal()

 {

     memset(dfn,,sizeof(dfn));

     memset(lowlink,,sizeof(lowlink));

     memset(scc_no,,sizeof(scc_no));

     dfn_clock=scc_cnt=;

     for(int i=; i<=n; i++)    if(!dfn[i])    DFS(i);   //深搜

     if(scc_cnt==)  return -;

     memset(chu,,sizeof(chu));

     memset(ru,,sizeof(ru));

     for(int i=; i<=n; i++)

         for(int j=; j<vect[i].size(); j++)  //统计出入度

             if(scc_no[i]!=scc_no[vect[i][j]])    chu[scc_no[i]]=ru[scc_no[vect[i][j]]]=true;//这里麻烦了点，小心点出错

     int c=, r=;

     for(int i=; i<=scc_cnt; i++)

     {

         if(!chu[i])    c++;

         if(!ru[i])     r++;

     }

     return max(c,r)-;

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     int a, b, t;

     cin>>t;

     while(t--)

     {

         scanf("%d%d",&n,&m);

         for(int i=; i<=n; i++) vect[i].clear();

         for(int i=; i<m; i++)

         {

             scanf("%d%d", &a, &b);

             vect[a].push_back(b);

         }

         printf("%d\n",cal());

     }

     return ;

 }