#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 5e5 + 5;
const int Mod = 1e9 + 7;
set <int> S[N]; 
vector <int> G[N];  
queue <pair <int, int>> Q; 
int T, n, m, u, v, tp, num, r[N], p[N], st[N], isl[N]; 

namespace io {
  const int SIZE = 1 << 22 | 1;
  char iBuf[SIZE], *iS, *iT, c;
  char oBuf[SIZE], *oS = oBuf, *oT = oBuf + SIZE;
  #define gc() (iS == iT ? iT = iBuf + fread(iS = iBuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++) : *iS++)
  template<class I> void read(I &x) {
    int f = 1;
    for(c = gc(); c < '0' || c > '9'; c = gc())
      if(c == '-') f = -1;
    for(x = 0; c >= '0' && c <= '9'; c = gc())
      x = (x << 3) + (x << 1) + (c & 15);
    x *= f;
  }
  inline void flush () {
    fwrite(oBuf, 1, oS - oBuf, stdout);
    oS = oBuf;
  }
  inline void putc(char x) {
    *oS++ = x;
    if(oS == oT) flush();
  }
  template<class I> void print(I x) {
    if(x < 0) putc('-'), x = -x;
    static char qu[55];
    char *tmp = qu;
    do *tmp++ = (x % 10) ^ '0'; while(x /= 10);
    while(tmp-- != qu) putc(*tmp);
    putc(' ');
  }
  struct flusher{ ~flusher() { flush(); } }_;
}

using io :: read; 
using io :: print; 

int inc (int a, int b) { return (a += b) >= Mod ? a - Mod : a; }
int dec (int a, int b) { return (a -= b) < 0 ? a + Mod : a; }
int mul (int a, int b) { return 1ll * a * b % Mod; }
int fpow (int a, int b) { int ans = 1; for ( ; b; a = mul(a, a), b >>= 1) if(b & 1) ans = mul(ans, a); return ans; }

namespace dsu {
  int l[N], r[N], fa[N]; 

  void reset () {
    rep(i, 1, n) l[i] = r[i] = fa[i] = i; 
  }
  int find (int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]); 
  }
  void Merge (int a, int b) {
    int x = find(a), y = find(b); 
    fa[x] = y, l[y] = l[x]; 
  }
}

void Merge (int u, int v) {
  r[u] = v, isl[v] = 0;
  dsu :: Merge(u, v);
  int w = dsu :: r[dsu :: find(u)], nw = 0;
  for (auto i : S[w]) {
    if(dsu :: find(i) == dsu :: find(w)) st[++tp] = i;
    else if(!isl[i]) break ; 
    else if(nw) { nw = 0; break ; }
    else nw = i; 
  }
  for ( ; tp; --tp) S[w].erase(st[tp]);
  if(nw) Q.push(make_pair(w, nw));  
}
bool check (int s) { 
  
}

int main () {
  read(T); 
  while (T--) {
    read(n), read(m), dsu :: reset(); 
    rep(i, 1, n) r[i] = 0, G[i].clear(), S[i].clear();
    rep(i, 1, m) {
      read(u), read(v);
      if(S[u].find(v) == S[u].end()) G[u].push_back(v), S[u].insert(v);
    }
    while (!Q.empty()) Q.pop(); 
    rep(i, 1, n) isl[i] = 1;
    rep(i, 1, n) if(G[i].size() == 1) Q.push(make_pair(i, G[i][0])); 
    while (!Q.empty()) {
      pair <int, int> u = Q.front(); Q.pop(); 
      if(isl[u.second]) Merge(u.first, u.second), ++num; 
    }
    if(num != n - 1) {
      int s1 = 0, s2 = 0; 
      rep(i, 1, n) if(!r[i]) {
        int cnt = 0, u; 
        for (auto j : G[i]) if(dsu :: find(i) != dsu :: find(j)) ++cnt, u = j;
        if(cnt == 1) {
          s1 = dsu :: l[dsu :: find(i)], s2 = dsu :: l[dsu :: find(u)]; 
          break ; 
        }
      }
      if(!s1) { puts("0"); continue ; }
      if(!check(s1)) {
        if(!check(s2)) { puts("0"); continue ; }
      } 
    }
    // Find A Valid Permutation.

  }
  return 0; 
}