import java.util.ArrayList;

class Main {
  public static void main(String[] args) {
    In in = new In();
    Out out = new Out();
    out.SysInit(); 
    test(in, out);
  }
  
   public static void test(In in, Out out) {
        in.open("public/custom.in");
        out.compareTo("public/custom.out");
        int numTests = in.readInt();
        
        for (int t = 0; t < numTests; t++) {
            int n = in.readInt(); 
            int m = in.readInt(); 
            int operation = in.readInt();
            
            int queryU = -1;  
            int queryV = -1;  
            if (operation == 1) {  
                queryU = in.readInt();
                queryV = in.readInt();
            }
            
            ArrayList<ArrayList<Integer>> E = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                E.add(new ArrayList<>());
            }
            
            for (int i = 0; i < m; i++) {
                int u = in.readInt();
                int v = in.readInt();
                E.get(u).add(v);
                E.get(v).add(u);
            }
            
            switch (operation) {
                case 0: 
                    boolean hasCycle = hasCycle(n, E);
                    out.println(hasCycle ? "true" : "false");
                    break;
                    
                case 1: 
                    boolean reachable = isReachable(n, E, queryU, queryV);  
                    out.println(reachable ? "true" : "false");
                    break;
                    
                case 2: 
                    int numComponents = countComponents(n, E);
                    out.println(numComponents);
                    break;
                    
                default:
                    out.println("Unknown operation");
            }
        }
    }
    
    // ==========================================================================================
    // Exercise 1 - Cycle Finding
    // ==========================================================================================
    
    // Determine if there exists an undirected cycle
    public static boolean hasCycle(int n, ArrayList<ArrayList<Integer>> E) {
        // TODO: Implement cycle detection
        boolean[] visited = new boolean[n];
        for (int i=0; i<n; i++) {
          if (!visited[i] && solveCycle(i, -1, visited, E)) return true;
        }
        return false;
    }
    
    // Modified DFS to detect cycles
    // Key: Keep track of parents to avoid false positives!
    public static boolean solveCycle(int curr, int par, boolean[] visited, ArrayList<ArrayList<Integer>> E) {
      if (visited[curr]) return true; // cycle detected!
      visited[curr] = true;
      for (int neigh: E.get(curr)) {
        if (neigh == par) continue; // careful with parents in DFS tree (false positives)
        if (solveCycle(neigh, curr, visited, E)) return true; // if neighbor detects cycle return true
      }
      return false; 
    }

    // ==========================================================================================
    // Exercise 2
    // ==========================================================================================

   // Determine if there is a path from u to v.
   // E = Adjacency list representation of the undirected graph
   // u = source vertex, v Target vertex
    public static boolean isReachable(int n, ArrayList<ArrayList<Integer>> E, int u, int v) {
        // TODO: Implement reachability check
        boolean[] visited = new boolean[n];
        return reaches(u, v, visited, E);
    }
    
    // check reachability of target using DFS
    public static boolean reaches(int curr, int target, boolean[] visited, ArrayList<ArrayList<Integer>> E) {
      if (curr == target) return true; // target found, return
      else if (visited[curr]) return false; // we've been down this path before, don't visit  again
      
      visited[curr] = true;
      // visit all neighbors
      for (int neigh: E.get(curr)) {
        if (reaches(neigh, target, visited, E)) return true;
      }
      return false;
    }

    // ==========================================================================================
    // Exercise 3
    // ==========================================================================================

    // // E = Adjacency list representation of the graph
    public static int countComponents(int n, ArrayList<ArrayList<Integer>> E) {
        // TODO: Implement component counting
        int count = 0;
        boolean[] visited = new boolean[n];
        // start new DFS from each unvisited vertex to find all connected components
        for (int i=0; i<n; i++) {
          if(!visited[i]) { // new connected component
            count++;
            solveCount(i, visited, E);
          }
        }
        return count;
    }
    
    // simple DFS with void return type
    public static void solveCount(int curr, boolean[] visited, ArrayList<ArrayList<Integer>> E) {
      if(visited[curr]) return;
      visited[curr] = true;
      for (int neigh: E.get(curr)) {
        solveCount(neigh, visited, E);
      }
    }
}