#include <cstdio>
#include <cstring>

using namespace std;

int n,m,t,a[601],b[601],v[18],cv[18],verificat;

void verifica()
{
    int i,aux;
    for(i=1;i<=n;++i)
        cv[i]=v[i];
    for(i=1;i<=m;++i)
    {
        if(cv[a[i]]>cv[b[i]])
        {
            aux=cv[a[i]];
            cv[a[i]]=cv[b[i]];
            cv[b[i]]=aux;
        }
    }
    for(i=1;i<n;++i)
        if(cv[i+1]<cv[i])
        {
            verificat=0;
            return;
        }
}


void back(int k)
{
    int i;
    if (verificat==0)
        return;
    if(k==n)
    {
        verifica();
        if (verificat==0) return;
    }
    else
    {
        for(i=0;i<=1;++i)
        {
            v[k+1]=i;
            back(k+1);
        }
    }
}


int main()
{
    int i,j;
    freopen("sortari.in","r",stdin);
    freopen("sortari.out","w",stdout);
    scanf("%d",&t);
    for(i=1;i<=t;++i)
    {
        scanf("%d %d",&n,&m);
        for(j=1;j<=m;++j)
            scanf("%d %d",&a[j],&b[j]);
        verificat=1;
        back(0);
        if(verificat) printf("1\n");
        else printf("0\n");
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
    }

    return 0;
}