#include <vector>
#include <algorithm>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <set>
#include <list>
#include <map>
 
using namespace std;
 
#define SZ(V) (int) V.size()
#define AIN(A, B, C) assert((B) <= (A) && (A) <= (C))
#define CLR(X) memset(X, 0, sizeof(X))
 
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII > VP;
typedef pair<LL, LL> PLL;
typedef pair<LL, int> PLI;
 
int n, m;
VI V[70004];
VI Vd[70004];
 
set<PII > edges;
VI pi;
 
int is_triangle(int v1, int v2, int v3) {
    return edges.find(PII(v1, v2)) != edges.end()
        && edges.find(PII(v2, v3)) != edges.end()
        && edges.find(PII(v3, v1)) != edges.end();
}
 
int neighbor[70005];
void removeFrom(set<int> &Q, VI &vc, int x, int v1, int v2) {
    if(!(vc[x] == 1)) return;
    vc[x] = 0;
    for (int z : V[x]) {
        neighbor[z]--;
        if (vc[z] == 0) continue;
        Q.erase(z);
        if (neighbor[z] == 2 && z != v1 && z != v2) Q.insert(z);
    }
}
 
void addIn(set<int> &Q, VI &vc, int x, int v1, int v2) {
    if(!(vc[x] == 0)) return;
    vc[x] = 1;
    if(neighbor[x] == 2) Q.insert(x);
    for (int z : V[x]) {
        neighbor[z]++;
        if (vc[z] == 0) continue;
        Q.erase(z);
        if(neighbor[z] == 2 && z != v1 && z != v2) Q.insert(z);
    }
}
 
int order(int v1, int v2, int vn) {
    CLR(neighbor);
    pi.resize(n);
    pi[0] = v1;
    pi[1] = v2;
    set<int> Q;
   // set<int> vc;
    VI vc(n + 1, 0);
    VI Gd(n + 1, 0);
    
    addIn(Q, vc, v1, v1, v2);
    addIn(Q, vc, v2, v1, v2);
    addIn(Q, vc, vn, v1, v2);
    
    for (int k = n; k >= 3; k--) {
        if (Q.empty()) return 0;
        int x = *Q.begin();
        Q.erase(x);
    
        removeFrom(Q, vc, x, v1, v2);
        for (int z : V[x]) {
            if (Gd[z] == 1) continue;
            if (z != v1 && z != v2)
                addIn(Q, vc, z, v1, v2);
        }
        Q.erase(v1);
        Q.erase(v2);
        Gd[x] = 1;
        pi[k - 1] = x;
    }
    return 1;
}
 
int mark[70004];
int marker = 0;
 
int embed(VI pi) {
    list<int> C0;
    map<int, list<int>::iterator > M;
    set<int> removed;
 
    M[pi[1]] = C0.insert(C0.begin(), pi[1]);
    M[pi[2]] = C0.insert(C0.begin(), pi[2]);
    M[pi[0]] = C0.insert(C0.begin(), pi[0]);
    removed.insert(pi[1]);
    removed.insert(pi[2]);
    removed.insert(pi[0]);
    
    for (int i = 3; i < n; i++) {
        int v = pi[i];
        removed.insert(v);
        VI candidate;
        
        marker++;
        for (int z : V[v]) {
            if (removed.find(z) == removed.end()) continue;
            mark[z] = marker;
            candidate.push_back(z);
        }
        
        int start = -1, end = -1;
        for (int c : candidate) {
            list<int>::iterator it = M[c];
            
            if (it == C0.begin()) {
                if (start != -1) return 0;
                start = c;
            } else {
                list<int>::iterator temp = it;
                temp--;
                if (mark[*temp] != marker) {
                    if (start != -1) return 0;
                    start = c;
                }
            }
            
            list<int>::iterator temp = it; temp++;
            if (temp == C0.end()) {
                if (end != -1) return 0;
                end = c;
            } else {
                if (mark[*temp] != marker) {
                    if (end != -1) return 0;
                    end = c;
                }
            }
        }
        
        if (start == -1) return 0;
        if (end == -1) return 0;
 
        for (int c : candidate) {
            if (c != start && c != end) {
                C0.erase(M[c]);
            }
        }
        M[v] = C0.insert(M[end], v);
    }
    
    return 1;
}
 
int recognize() {
    if (n == 1 && m == 0) return 1;
    if (n == 2 && m == 1) return 1;
    if (n == 3 && m == 3) return 1;
    if (n <= 3) return 0;
    
    if (m != 3 * n - 6) return 0;
    
    int v1;
    for (v1 = 1; v1 <= n; v1++) {
        if (SZ(V[v1]) < 3) return 0;
    }
    
    for (v1 = 1; v1 <= n; v1++) {
        if (SZ(V[v1]) <= 5) {
            break;
        }
    }
    
    if (v1 > n) return 0;
    int v2 = V[v1][SZ(V[v1]) - 1];
    for (int i = 0; i < SZ(V[v1]) - 2; i++) {
        int vn = V[v1][i];
        if (is_triangle(v1, v2, vn)) {
            pi.clear();
            fprintf(stderr, ">");
            if (!order(v1, v2, vn)) continue;
            fprintf(stderr, "<");
            fprintf(stderr, "(");
            if (!embed(pi)) continue;
            fprintf(stderr, ")");
            return 1;
        }
    }
    return 0;
}
 
int main() {
    int T;
    scanf("%d", &T);
    AIN(T, 1, 10);
    while(T--) {
        scanf("%d %d", &n, &m);
        AIN(n, 1, 70000);
        AIN(m, 0, 300000);
        
        edges.clear();
        for (int i = 1; i <= n; i++) V[i].clear();
 
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            V[u].push_back(v);
            V[v].push_back(u);
            assert(u != v);
            assert(edges.find(PII(u, v)) == edges.end());
            edges.insert(PII(u, v));
            edges.insert(PII(v, u));
        }
        
        printf("%d\n", recognize());
    }
    return 0;
}