#include <iostream>
#include <vector>

using namespace std;

int licznik;
int test;
int n;
int m;
int kolorki = 0;
int kolory[1000100];
vector <int> graf[1000100];
int visited[1000100];

void CLEARfunction()
{
	for (int i = 0; i < n+2 ; i++)
	{
	    kolory[i] = 0;
	    kolorki = 1;
		visited[i] = 0;
		graf[i].clear();
	}
}

void DFSfunction(int u)
{
    kolory[u] = kolorki;
	visited[u] = 1;
	kolorki ++;
	for (int i = 0; i < graf[u].size(); i++)
	{
		int v = graf[u][i];
            if(kolory[v] == 0)
            {
                kolory[v] = kolorki;
            }

		    if((kolory[u]%2 == 0 && kolory[v]%2 == 0) || (kolory[u]%2 == 1 && kolory[v]%2 == 1))
            {
                licznik++;
            }

		if (visited[v] == 0)
		{
		    if((kolory[u]%2 == 0 && kolory[v]%2 == 0) || (kolory[u]%2 == 1 && kolory[v]%2 == 1))
            {
                licznik++;
            }
            DFSfunction(v);
		}
	}
}

void DFS()
{
	cin >> n;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int a;
		int b;
		cin >> a;
		cin >> b;
		graf[a].push_back(b);
		graf[b].push_back(a);
	}

	DFSfunction(1);
}

void CHECKfunction()
{
    /*for(int i = 1 ; i <= n ; i++)
    {
        cout << kolory[i] << " ";
    }
    cout << "\n";*/
	if(licznik > 0)
	{
		cout << "NIE\n";
	}
	else
	{
		cout << "TAK\n";
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> test;
	for (int t = 0; t < test; t++)
	{
		DFS();

		CHECKfunction();

		CLEARfunction();
	}
	return 0;
}