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
#ifdef USE_PALI
#include <pali.hpp>
#else
#include <bits/stdc++.h>
typedef unsigned int uint;
#endif
using namespace std;

struct Node
{
  uint color;
  vector<uint> edges;

  Node() : color(), edges() {}
};

struct Graph
{
  vector<Node> nodes;

  Graph(uint nnodes) : nodes(vector<Node>(nnodes)) {}
};

struct Checker
{
  Graph& graph;

  vector<bool> visited;
  bool failed;

  vector<uint> path_color_count;

  Checker(Graph& graph_, uint ncolors)
      : graph(graph_), visited(vector<bool>(graph_.nodes.size())), failed(),
        path_color_count(vector<uint>(ncolors + 1))
  {
  }

  bool check()
  {
    uint best = numeric_limits<uint>::max();
    uint start = 0;
    for (uint i = 0; i < graph.nodes.size() && best > 1; ++i) {
      uint nedges = static_cast<uint>(graph.nodes[i].edges.size());
      if (best > nedges) {
        best = nedges;
        start = i;
      }
    }
    traverse(start, graph.nodes[start].color);
    return !failed;
  }

  void traverse(uint node, uint path_prev_color)
  {
    visited[node] = true;
    uint color = graph.nodes[node].color;
    if (color != path_prev_color && path_color_count[color] > 0) {
      failed = true;
      return;
    }
    ++path_color_count[color];
    for (uint e : graph.nodes[node].edges) {
      if (!visited[e])
        traverse(e, color);
      if (failed)
        return;
    }
    --path_color_count[color];
  }
};

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  uint T;
  cin >> T;
  for (uint t = 0; t < T; ++t) {
    uint N, M, K;
    cin >> N >> M >> K;

    Graph graph(N);
    for (uint i = 0; i < N; ++i)
      cin >> graph.nodes[i].color;
    for (uint i = 0; i < M; ++i) {
      uint u, v;
      cin >> u >> v;
      --u;
      --v;
      graph.nodes[u].edges.push_back(v);
      graph.nodes[v].edges.push_back(u);
    }

    Checker checker(graph, K);
    cout << ((checker.check()) ? "TAK" : "NIE") << '\n';
  }
}