#include <iostream>
#include <vector>
using namespace std;

#define N 100001

bool odw[N];
vector <int> G[N];
int ile[N];

int main()
{
    ios_base::sync_with_stdio(false);
    int c;
    cin >> c;
    for(int k = 0 ; k < c ; k++)
    {
        int n, m;
        cin >> n >> m;

        for(int i = 0 ; i < m ; i++)
        {
            int a, b;
            cin >> a >> b;
            ile[a]++;
            ile[b]++;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        bool czy = true;
        int n1 = n;
        while(czy)
        {
            czy = false;
            for(int i = 1 ; i <= n ; i++)
            {
                if(odw[i] == false)
                {
                    if(ile[i] < 2)
                    {
                        if(G[i].size() != 0)
                            ile[G[i][0]]--;
                        n1--;
                        odw[i] = true;
                        czy = true;
                    }
                }
            }
        }
        if(n1 == 0)
            cout << "NIE\n";
        else
            cout << "TAK\n";

        for(int i = 1 ; i <= n ; i++)
        {
            G[i].clear();
            ile[i] = 0;
            odw[i] = false;
        }
    }
}