import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class XYZ{

    final static int WHITE=0,GREY=1,BLACK=2;
    static boolean vis[]=new boolean[100000];
    static int colour[]=new int[100000];
    static ArrayList<Integer> adj[]=new ArrayList[100000];
   static int ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int t=Integer.parseInt(br.readLine()),n,m;
        String[]s;
        for (int i = 0; i < 100000; i++) {
            adj[i]=new ArrayList<>();
        }
        while (t-->0){
            s=br.readLine().split("\\s");
            n=Integer.parseInt(s[0]);
            m=Integer.parseInt(s[1]);
            for (int i = 0; i < n; i++) {
                adj[i].clear();
            }
            Arrays.fill(colour,0,n,WHITE);
            Arrays.fill(vis,0,n,false);
            for (int i = 0; i < m; i++) {
                s=br.readLine().split("\\s");
                int u=Integer.parseInt(s[0])-1;
                int v=Integer.parseInt(s[1])-1;
                adj[u].add(v);
            }

            System.out.println(solve(adj,n));
        }
    }

    private static int solve(ArrayList<Integer>[] adj, int n) {
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                ans =0;
                dfs(i);
                if (ans==1)
                    return 0;
            }
        }
        return 1;
    }

    private static void dfs(int u) {
        colour[u]=GREY;
        vis[u]=true;

        for (int i = 0; i < adj[u].size(); i++) {
            int v=adj[u].get(i);
            if (colour[v]==GREY){
                ans=1;
                return;
            }
            if (!vis[v])
                 dfs(v);
        }
        colour[u]=BLACK;
    }

}