OI XXVI - rem (Faster)

// https://szkopul.edu.pl/problemset/problem/xNjwUvwdHQoQTFBrmyG8vD1O/site/?key=statement

#include <bits/stdc++.h>

constexpr int sizik = 150 * 1001;

#define ar std::array
#define pr std::std::pair

namespace two_sat {
inline int lit_to_node(int lit) {
    int v = std::abs(lit) - 1;
    return 2 * v + (lit < 0 ? 1 : 0);
}
inline int neg_node(int node) {
    return node ^ 1;
}
struct CSR {
    int V;
    std::vector<int> head;
    std::vector<int> to;
    CSR(int V = 0) : V(V), head(V + 1, 0) {}
    inline int size() const { return V; }
    inline const int* row_begin(int v) const { return &to[head[v]]; }
    inline const int* row_end(int v) const { return &to[head[v + 1]]; }
    inline int row_size(int v) const { return head[v + 1] - head[v]; }
};

static CSR build_csr(int V, std::vector<std::pair<int, int>>& edges) {
    CSR g(V);
    int E = (int)edges.size();
    for (auto& e : edges)
        ++g.head[e.first + 1];
    for (int i = 1; i <= V; ++i)
        g.head[i] += g.head[i - 1];
    g.to.resize(E);
    std::vector<int> cursor(g.head.begin(), g.head.end());
    for (auto& e : edges) {
        int u = e.first, v = e.second;
        g.to[cursor[u]++] = v;
    }
    return g;
}

std::pair<bool, std::vector<char>> solve(const std::vector<std::pair<int, int>>& clauses, int Nvars) {
    int V = 2 * Nvars;
    std::vector<std::pair<int, int>> edges;
    edges.reserve(2 * clauses.size());
    std::vector<std::pair<int, int>> redges;
    redges.reserve(2 * clauses.size());

    for (auto& cl : clauses) {
        int a = cl.first, b = cl.second;
        int na = lit_to_node(a), nb = lit_to_node(b);
        int n_na = neg_node(na), n_nb = neg_node(nb);
        edges.emplace_back(n_na, nb);
        redges.emplace_back(nb, n_na);
        edges.emplace_back(n_nb, na);
        redges.emplace_back(na, n_nb);
    }

    CSR G = build_csr(V, edges);
    CSR GR = build_csr(V, redges);

    std::vector<char> used(V, 0);
    std::vector<int> order;
    order.reserve(V);

    std::vector<std::pair<int, int>> st;
    st.reserve(1024);

    for (int s = 0; s < V; ++s) {
        if (used[s]) continue;
        st.clear();
        used[s] = 1;
        st.emplace_back(s, 0);
        while (!st.empty()) {
            int v = st.back().first;
            int& it = st.back().second;
            int row_begin = G.head[v], row_end = G.head[v + 1];
            if (row_begin + it < row_end) {
                int to = G.to[row_begin + it];
                ++it;
                if (!used[to]) {
                    used[to] = 1;
                    st.emplace_back(to, 0);
                }
            } else {
                order.push_back(v);
                st.pop_back();
            }
        }
    }

    std::vector<int> comp(V, -1);
    int cid = 0;
    std::vector<int> st2;
    st2.reserve(1024);
    for (int i = (int)order.size() - 1; i >= 0; --i) {
        int v = order[i];
        if (comp[v] != -1) continue;
        st2.clear();
        st2.push_back(v);
        comp[v] = cid;
        while (!st2.empty()) {
            int u = st2.back();
            st2.pop_back();
            int rb = GR.head[u], re = GR.head[u + 1];
            for (int idx = rb; idx < re; ++idx) {
                int to = GR.to[idx];
                if (comp[to] == -1) {
                    comp[to] = cid;
                    st2.push_back(to);
                }
            }
        }
        ++cid;
    }

    for (int i = 0; i < Nvars; ++i) {
        if (comp[2 * i] == comp[2 * i ^ 1]) return {false, {}};
    }

    std::vector<char> assign(Nvars, 0);
    for (int i = 0; i < Nvars; ++i) {
        assign[i] = (comp[2 * i] > comp[2 * i ^ 1]) ? 1 : 0;
    }
    return {true, assign};
}
} // namespace two_sat

int a[sizik];

void solve() {
    int n, k;
    std::cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];

    std::vector<std::array<int, 3>> triples;
    triples.reserve(n - 1);
    for (int i = 1; i <= n - 1; ++i) {
        triples.push_back({a[i], a[i + 1], i});
    }
    sort(triples.begin(), triples.end(), [](const auto& x, const auto& y) {
        if (x[0] != y[0]) return x[0] < y[0];
        return x[1] < y[1];
    });

    std::vector<std::vector<int>> groups;
    groups.reserve(triples.size());
    for (size_t i = 0; i < triples.size();) {
        size_t j = i + 1;
        while (j < triples.size() && triples[j][0] == triples[i][0] && triples[j][1] == triples[i][1])
            ++j;
        groups.emplace_back();
        auto& vec = groups.back();
        vec.reserve(j - i);
        for (size_t t = i; t < j; ++t)
            vec.push_back(triples[t][2]);
        i = j;
    }

    int estimated_clauses = n + 3 * (n - 1);
    std::vector<std::pair<int, int>> clauses;
    clauses.reserve(estimated_clauses);

    int ziomeczki = n - 1;
    clauses.emplace_back(1, 1);
    for (int i = 2; i < n; ++i)
        clauses.emplace_back(i - 1, i);
    clauses.emplace_back(n - 1, n - 1);

    for (auto& vec : groups) {
        int w = (int)vec.size();
        if (w <= 1) continue;
        if (w == 2) {
            clauses.emplace_back(-vec[0], -vec[1]);
            continue;
        }
        clauses.emplace_back(-vec[0], ziomeczki + 1);
        for (int i = 2; i <= w - 1; ++i) {
            clauses.emplace_back(-vec[i - 1], ziomeczki + i);
            clauses.emplace_back(-(ziomeczki + i - 1), ziomeczki + i);
        }
        for (int i = 2; i <= w; ++i) {
            clauses.emplace_back(-vec[i - 1], -(ziomeczki + i - 1));
        }
        ziomeczki += (w - 1);
    }

    auto res = two_sat::solve(clauses, ziomeczki);
    if (!res.first)
        std::cout << "NIE\n";
    else
        std::cout << "TAK\n";
}

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

    for (; T > 0; T--) {
        solve();
    }

    return 0;
}