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 testNum = in.readInt(); // number of tests
    for (int test = 0; test < testNum; test++) {
      int n = in.readInt();
      int m = in.readInt();

      ArrayList<ArrayList<Integer>> E = new ArrayList<ArrayList<Integer>>(n);
      for (int i = 0; i < n; i++) { // initialization with empty arrays
        E.add(new ArrayList<Integer>());
      }
      for (int i = 0; i < m; i++) { // read edges
        int u = in.readInt();
        int v = in.readInt();
        E.get(u).add(v);
        E.get(v).add(u);
      }
      out.println(eulerian(n, m, E));
    }
  }
  
  // E is the adjacency list representation!
  // E.get(i).get(j) is the j-th neighbor of vertex i
  // E.get(i).size() is the number of neighbors of vertex i
  public static boolean eulerian(int n, int m, ArrayList<ArrayList<Integer>> E) {
    // TODO
    int[] deg = new int[n];
    boolean[] visited = new boolean[n];
    
    // find first non-isolated vertex to start DFS from
    for (int i=0; i<n; i++) {
      if (E.get(i).size() > 0) {
        connected(i, visited, E);
        break;
      }
    }
    
    for (int i=0; i<n; i++) {
      deg[i] = E.get(i).size(); // size of adjacency list
      // check if either odd degree or (not visited and not-isolated (deg != 0))
      if (deg[i] % 2 == 1 || (!visited[i] && deg[i] != 0)) return false;
    }
    
    return true;
  }
  
  public static void connected(int curr, boolean[] visited, ArrayList<ArrayList<Integer>> E) {
    // return if already visited
    if (visited[curr]) return;
    visited[curr] = true;
    
    // visit all neighbors of curr
    for (int neigh: E.get(curr)) { 
      connected(neigh, visited, E);
    }
  }
}