#include<iostream>

#include<vector>

#include<cstring>

using namespace std;

int book[];

vector<int>v[];

bool dfs(int x,int c)

{

    book[x]=c;

    for(int i=;i<v[x].size();i++){

        if(book[v[x][i]]==c){return false;}

        if(book[v[x][i]]==&&!dfs(v[x][i],-c)){return false;}

    }

    return true;

}

int main()

{

    int T;

    cin>>T;

    int n,m,x,y;

    while(T--){

        memset(book,,sizeof(book));

        cin>>n>>m;

        for(int i=;i<m;i++){

            cin>>x>>y;

            v[x].push_back(y);

            v[y].push_back(x);

        }

        int flag=;

        for(int i=;i<=n;i++){

            if(!book[i]&&!dfs(i,)){flag=;break;}

        }

        if(flag){cout<<"非二分图"<<endl;}

        else cout<<"二分图"<<endl;

        for(int i=;i<=n;i++){

            v[i]=vector<int>();

        }

    }

}