We are given an undirected graph containing N vertices, initial containing no edges. The system must process Q online queries of two distinct types:

• Type 1: Establish an undirected edge between vertices u and v.
• Type 2: Identify the k-th largest vertex identifier within the connected component containing vertex x. Return -1 if the component contains fewer than k vertices.

Constraints: N, Q ≤ 2×10^5, 1 ≤ k ≤ 10.

Bounded k Optimization Using Vector Maintenance

Given the strict upper bound on k, we can efficient track the largest identifiers within each connected component without storing the complete vertex set. A Disjoint Set Union (DSU) structure naturally manages dynamic connectivity, while each representative node maintains a container holding at most the k largest vertex indices from its component.

When two components merge, their containers are combined, sorted in descending order, and truncated to retain only the top k values. Path compression ensures that root lookups remain nearly constant time. Since the container size never exceeds 10, the merge and sorting operations are bounded by O(k log k), which fits comfortably within typical time limits.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

class ComponentTracker {
private:
    std::vector<int> parent;
    std::vector<std::vector<int>> topValues;
    static constexpr int LIMIT = 10;

public:
    explicit ComponentTracker(int n) {
        parent.resize(n + 1);
        topValues.resize(n + 1);
        std::iota(parent.begin(), parent.end(), 0);
        for (int i = 1; i <= n; ++i) {
            topValues[i].push_back(i);
        }
    }

    int findRoot(int node) {
        if (parent[node] == node) return node;
        return parent[node] = findRoot(parent[node]);
    }

    void unite(int u, int v) {
        int rootU = findRoot(u);
        int rootV = findRoot(v);
        if (rootU != rootV) {
            if (topValues[rootU].size() < topValues[rootV].size()) {
                std::swap(rootU, rootV);
            }
            topValues[rootU].insert(
                topValues[rootU].end(),
                topValues[rootV].begin(),
                topValues[rootV].end()
            );
            std::sort(topValues[rootU].begin(), topValues[rootU].end(), std::greater<int>());
            if (static_cast<int>(topValues[rootU].size()) > LIMIT) {
                topValues[rootU].resize(LIMIT);
            }
            parent[rootV] = rootU;
        }
    }

    int queryKthLargest(int u, int k) const {
        int root = findRoot(u);
        if (k > static_cast<int>(topValues[root].size())) return -1;
        return topValues[root][k - 1];
    }
};

void processQueries() {
    int N, Q;
    if (!(std::cin >> N >> Q)) return;

    ComponentTracker tracker(N);
    for (int i = 0; i < Q; ++i) {
        int type, u, v;
        std::cin >> type >> u >> v;
        if (type == 1) {
            tracker.unite(u, v);
        } else {
            std::cout << tracker.queryKthLargest(u, v) << '\n';
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    processQueries();
    return 0;
}

Generalization for Arbitrary k Using Balanced Trees

If k scales up to N, maintaining a sorted vector becomes impractical due to linear merge costs. Instead, we can utilize an Order Statistic Tree, such as a Treap, to manage elements within each component. This structure supports insertion and k-th element retrieval in logarithmic time. To maintain efficiency during component merges, we aply heuristic merging: always insert the elements of the smaller tree into the larger tree. This guarantees an amortized complexity of O(log^2 N) per merge operation.

The following implementation provides a self-contained Treap with split/merge operations, integrated into the DSU framework.

#include <iostream>
#include <vector>
#include <chrono>
#include <numeric>

struct Node {
    int val, priority, size;
    Node *left, *right;
    Node(int v) : val(v), priority((int)std::chrono::steady_clock::now().time_since_epoch().count()), size(1), left(nullptr), right(nullptr) {}
};

void updateSize(Node* t) {
    if (t) t->size = 1 + (t->left ? t->left->size : 0) + (t->right ? t->right->size : 0);
}

void split(Node* t, Node*& l, Node*& r, int key) {
    if (!t) { l = r = nullptr; return; }
    if (t->val <= key) {
        split(t->right, t->right, r, key);
        l = t;
    } else {
        split(t->left, l, t->left, key);
        r = t;
    }
    updateSize(t);
}

void merge(Node*& t, Node* l, Node* r) {
    if (!l || !r) t = l ? l : r;
    else if (l->priority > r->priority) {
        merge(l->right, l->right, r);
        t = l;
    } else {
        merge(r->left, l, r->left);
        t = r;
    }
    updateSize(t);
}

void insertNode(Node*& root, int val) {
    Node *l, *r;
    split(root, l, r, val);
    merge(l, l, new Node(val));
    merge(root, l, r);
}

int getKthLargest(Node* t, int k) {
    if (!t || k > t->size) return -1;
    int rightSize = t->right ? t->right->size : 0;
    if (k == rightSize + 1) return t->val;
    if (k <= rightSize) return getKthLargest(t->right, k);
    return getKthLargest(t->left, k - rightSize - 1);
}

void destroyTree(Node* t) {
    if (!t) return;
    destroyTree(t->left);
    destroyTree(t->right);
    delete t;
}

class GraphManager {
private:
    std::vector<int> parent;
    std::vector<Node*> trees;
public:
    GraphManager(int n) : parent(n + 1), trees(n + 1, nullptr) {
        std::iota(parent.begin(), parent.end(), 0);
        for (int i = 1; i <= n; ++i) trees[i] = new Node(i);
    }

    int findRoot(int x) {
        return parent[x] == x ? x : parent[x] = findRoot(parent[x]);
    }

    void unite(int u, int v) {
        int rootU = findRoot(u);
        int rootV = findRoot(v);
        if (rootU != rootV) {
            if (trees[rootU]->size < trees[rootV]->size) std::swap(rootU, rootV);
            auto collectInorder = [](Node* t, std::vector<int>& res) {
                if (!t) return;
                collectInorder(t->left, res);
                res.push_back(t->val);
                collectInorder(t->right, res);
            };
            std::vector<int> vals;
            collectInorder(trees[rootV], vals);
            for (int v : vals) insertNode(trees[rootU], v);
            destroyTree(trees[rootV]);
            trees[rootV] = nullptr;
            parent[rootV] = rootU;
        }
    }

    int queryKth(int u, int k) {
        int root = findRoot(u);
        return getKthLargest(trees[root], k);
    }

    ~GraphManager() {
        for (auto t : trees) destroyTree(t);
    }
};

void processLargeQueries() {
    int N, Q;
    if (!(std::cin >> N >> Q)) return;
    GraphManager manager(N);
    for (int i = 0; i < Q; ++i) {
        int type, u, v;
        std::cin >> type >> u >> v;
        if (type == 1) manager.unite(u, v);
        else std::cout << manager.queryKth(u, v) << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    processLargeQueries();
    return 0;
}