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
import sys
from collections import deque

def rozwiaz():
    dane = sys.stdin.buffer.read().split()
    idx = 0
    t = int(dane[idx]); idx += 1
    wyniki = []

    for _ in range(t):
        n, m, k = int(dane[idx]), int(dane[idx+1]), int(dane[idx+2])
        idx += 3

        a = [int(dane[idx+i])-1 for i in range(n)]  # numery partii 
        idx += n

        miasta_partii = [[] for _ in range(k)]
        for i in range(n):
            miasta_partii[a[i]].append(i)

        sasiedzi = [[] for _ in range(n)]
        for _ in range(m):
            u, v = int(dane[idx])-1, int(dane[idx+1])-1
            idx += 2
            sasiedzi[u].append(v)
            sasiedzi[v].append(u)
            
        rodzic = list(range(n))
        rozmiar = [1] * n
        partie_w_komponencie = [{a[i]} for i in range(n)]  
        liczba_komponentow = [len(miasta_partii[p]) for p in range(k)]  # ile komponanetow ma kqzda partia
        aktywna = [False] * k
        kolejka = deque()

        def znajdz(x):
            while rodzic[x] != x:
                rodzic[x] = rodzic[rodzic[x]]
                x = rodzic[x]
            return x

        def polacz(x, y):
            rx, ry = znajdz(x), znajdz(y)
            if rx == ry:
                return
            if rozmiar[rx] < rozmiar[ry]:
                rx, ry = ry, rx
            rodzic[ry] = rx
            rozmiar[rx] += rozmiar[ry]
            for p in partie_w_komponencie[ry]:
                if p in partie_w_komponencie[rx]:
                    liczba_komponentow[p] -= 1
                    if liczba_komponentow[p] <= 1 and not aktywna[p]:
                        kolejka.append(p)
                else:
                    partie_w_komponencie[rx].add(p)
            partie_w_komponencie[ry] = None

        for i in range(n):
            for j in sasiedzi[i]:
                if a[j] == a[i]:
                    polacz(i, j)

        for p in range(k):
            if liczba_komponentow[p] <= 1:
                kolejka.append(p)

        # przetwrzanie od konca kolejnosci kampanii
        przetworzone = 0
        while kolejka:
            p = kolejka.popleft()
            if aktywna[p]:
                continue
            aktywna[p] = True
            przetworzone += 1
            # krawedzie do nieaktyw parti
            for u in miasta_partii[p]:
                for v in sasiedzi[u]:
                    if not aktywna[a[v]]:
                        polacz(u, v)

        wyniki.append("TAK" if przetworzone == k else "NIE")

    sys.stdout.write('\n'.join(wyniki) + '\n')

rozwiaz()