UnionFind を用いて解くことができます．\(K=10\) として，各連結成分ごとに，その連結成分に含まれる頂点のうち頂点番号が大きい上位 \(K\) 個を持たせておきます．クエリ \(1\) の処理では，\(2\) つの連結成分の頂点番号上位 \(K\) 個のマージを \(O(K \log K)\) で行うことができます．クエリ \(2\) に対しては\(O(1)\) で \(k\) 番目に大きい頂点番号を取得することができます．

実装方法はいくつか考えられますが，UnionFind の構造体の中を直接いじるのが楽かつ汎用的だと筆者は思っています．(個人差がありますので，他の上級者の実装例も参考にしてみてください．) 筆者の実装方法では、具体的にいじる場所は主に \(2\) 箇所です．

• UnionFind の初期化において，必要な情報を追加する
• UnionFind の merge で，一方（子になる方）の情報をもう一方（親になる方）に情報をマージさせる

詳しくは以下の実装例を参考にしてください．

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        # 各連結成分に含まれる頂点の上位 10 個を管理する
        # 最初の時点では，各連結成分の頂点は 1 つずつ
        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

        # 親 x に子 y の情報をマージする
        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])