1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import sys
class Graph:
    def __init__(self, n):
        self.count = n
        self.neighbours = dict()
        self.rep=dict([])
        for i in range(n+1):
            self.rep[i] = i
        for i in range(n+1):
            self.neighbours[i] = set([])
    def add(self,u,v):
        self.neighbours[u].add(v)
        self.neighbours[v].add(u)
    def rank(self,v):
        return len(self.neighbours[v])
    def merge(self, u,v):
        u = self.rep[u]
        v = self.rep[v]
        if(u==v):
            return
        self.count -=1
        if(self.rank(u) < self.rank(v)):
            h=u
            u=v
            v=h
        #print(f"merging {u} {self.neighbours[u]} and {v} {self.neighbours[v]}")
        self.neighbours[u]= self.neighbours[u].union(self.neighbours[v])
        #print(self.neighbours[u])
        for i in self.neighbours[v]:
            self.neighbours[i].add(u)
            self.neighbours[i].remove(v)
        del self.neighbours[v]
        self.rep[v] = u
        return u 
        

def get_ints(): 
    return list(map(int, sys.stdin.readline().strip().split()))
MAXN = 10**5+10

def main():
    t = int(sys.stdin.readline())
    for qwertyuiopasdfghjklzxcvbnm in range(t):
        num_areas = dict()
        coherent_area = []
        n,m,k = get_ints()
        for i in range(k+1):
            num_areas[i] = 0
        g = Graph(n)
        winner = get_ints()
        for i in range(n):
            num_areas[winner[i]] += 1
        for i in range(n):
            if(num_areas[winner[i]] == 1):
                coherent_area.append(i)
        for _ in range(m):
            a,b = get_ints()
            a-=1
            b-=1
            g.add(a,b)
            g.add(b,a)
        for u in range(n):
            if u in g.neighbours.keys():
                #print(g.neighbours[u])
                to_merge = []
                for v in g.neighbours[u]:
                    if winner[u] == winner[v]:
                        to_merge.append(v)
                h = u 
                for v in to_merge:
                    h = g.merge(h,v)
                    num_areas[winner[h]] -=1
                    if(num_areas[winner[h]] == 1):
                        coherent_area.append(h)
                #print(g.neighbours[u])
        #print(f"coherent area {coherent_area}")
        deleted =set([])
        while len(coherent_area):
            u = coherent_area.pop()
            col = winner[u]
            #print(f"deleting {u} {g.neighbours[u]}")
            to_merge = []
            for v in g.neighbours[u]:
                if v in deleted:
                    to_merge.append(v)
            for v in to_merge:
                u = g.merge(u,v)
            rep=dict([])
            to_merge = []
            for v in g.neighbours[u]:
                if not v in deleted:
                    if winner[v] in rep.keys():
                        to_merge.append((rep[winner[v]],v))
                    else:
                        rep[winner[v]] = v
            for i,j in to_merge:
                h = g.merge(i,j)
                num_areas[winner[h]] -=1
                if(num_areas[winner[h]] == 1):
                    coherent_area.append(h)
            deleted.add(col)
            #print(f"num areas {num_areas}")
            #print(f"coherent area {coherent_area}")
            #print(f"deleted {deleted}")
        if deleted==set(winner):
            print("TAK")
        else:
            print("NIE")
        
        

if __name__ == "__main__":
    main()