#include<bits/stdc++.h>
using namespace std;
vector<int> g[1000007];
bool odwiedzone[1000007], cykliczny;
int t, n, m, a, b;
void dfs(int u, int z)
{
    odwiedzone[u] = true;
    for(int i=0; i<g[u].size(); i++)
        {
            int v = g[u][i];
            if(odwiedzone[v] == false)
            {
                dfs(v, u);
            }
            else if(z!=v)
            {
                cykliczny = true;
            }
        }
}

int main()
{
    cin >> t;
    while (t--)
        {
            cin >> n >> m;
            for(int i=0; i<m ; i++)
            {
                cin >> a >> b;
                g[a].push_back(b);
                g[b].push_back(a);
            }
            for(int i=1; i<=n; i++)
            {
                if(odwiedzone[i]==false)
                {
                    dfs(i, -1);
                }
            }
            if(cykliczny==true)
            {
                cout << "TAK" << "\n";
            }
            else
            {
                cout << "NIE" << "\n";
            }
        }
    return 0;
}