OIG XI - met

// https://szkopul.edu.pl/problemset/problem/dLUwClaxLgW6EcwH1JosIGms/site/?key=statement
// XI OIG — Zawody indywidualne, etap I.

#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>

constexpr int sizik = 2 * 100 * 1001;

int rep[sizik];

int Find(int a) {
    if (rep[a] == a) {
        return a;
    }

    int res = Find(rep[a]);

    rep[a] = res;
    return rep[a];
}

void Union(int a, int b) {
    int r1 = Find(a), r2 = Find(b);

    rep[r1] = r2;
}

std::unordered_map<int, std::vector<int>> m1, m2;

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

    int n, t;
    std::cin >> n >> t;

    for (int i = 1; i <= n; i++) {
        int a, b;
        std::cin >> a >> b;

        m1[a].push_back(i);
        m2[b].push_back(i);

        rep[i] = i;
    }

    for (const auto& [cord, vec] : m1) {
        int el = vec[0];

        for (int i = 1; i < vec.size(); i++) {
            Union(el, vec[i]);
        }
    }

    for (const auto& [cord, vec] : m2) {
        int el = vec[0];

        for (int i = 1; i < vec.size(); i++) {
            Union(el, vec[i]);
        }
    }

    for (; t > 0; t--) {
        int a, b;
        std::cin >> a >> b;

        a = Find(a);
        b = Find(b);

        if (a == b) {
            std::cout << "TAK\n";
        } else {
            std::cout << "NIE\n";
        }
    }

    return 0;
}