import sys

from collections import defaultdict
from queue import Queue

#alorytm BFS

def BFS(start,graph,color):
    global tak
    tak=True
    Q = Queue()
    color[start]=1
    Q.put(start)

    while not(Q.empty()):
        v=Q.get()

        for i in range(len(graph[v])):
            if not(color[graph[v][i]]):
                color[graph[v][i]]=(-1)*color[v]
                Q.put(graph[v][i])
            elif (color[graph[v][i]] == color[v]):
                print("NIE")
                tak=False
                return
        
#wczytanie grafu jako lista sąsiedztwa

z=int(input())
for j in range(1,z+1):
    
    n, m = input().split()
    n = int(n)
    m = int(m)

    graph = defaultdict(list)
    color = [0]*(n+1)

    for i in range(m):
        a, b = input().split()
        a = int(a)
        b = int(b) 

        graph[a].append(b)
        graph[b].append(a)
        
    #główna część

    for w in range(1,n+1):
        if not(color[w]):        
            BFS(w,graph,color)
        if not(tak):
            break

    if tak:
        print("TAK")
