This problem can be solved with a Disjoint Set Union (DSU). FOr each connected component, maintain the \(K\) vertices with the largest vertex numbers. On query \(1\), one can merge the two lists of \(K\) vertices with the largest vertex numbers for the two connected components in \(O(K \log K)\) time. On query \(2\), the \(k\)-th largest vertex number can be retrieved in \(O(1)\) time.

There are several implementation approach. The author thinks directly modifying the struct of the DSU would be simple and versatile. Specifically, two places should be modified:

• On initializing DSU, add necessary data.
• On merging two vertices, merge the information of one of them (that becomes the children) into the other (that becomes the parent).

For more details, please refer to the sample code below.

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        # Manage the 10 largest vertices in each connected components
        # Initially, each connected component has one vertex
        self.member = [[i] for i in range(n)]

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

        # Merge the information of children y into that of parent x
        self.member[x] += self.member[y]
        self.member[x] = sorted(self.member[x], reverse=True)[:10]


N, Q = map(int, input().split())
uf = UnionFind(N + 1)
for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        u, v = query[1:]
        uf.merge(u, v)
    else:
        v, k = query[1:]
        v = uf.find(v)
        if len(uf.member[v]) < k:
            print(-1)
        else:
            print(uf.member[v][k - 1])