AT_abc372_e [ABC372E] K-th Largest Connected Components

[problemUrl]: https://atcoder.jp/contests/abc372/tasks/abc372_e $ N $ 頂点 $ 0 $ 辺の無向グラフがあります。頂点には $ 1 $ から $ N $ の番号がつけられています。 $ Q $ 個のクエリが与えられるので、与えられた順に処理してください。各クエリは以下の $ 2 $ 種類のいずれかです。 - タイプ $ 1 $ : `1 u v` の形式で与えられる。頂点 $ u $ と頂点 $ v $ の間に辺を追加する。 - タイプ $ 2 $ : `2 v k` の形式で与えられる。頂点 $ v $ と連結な頂点の中で、$ k $ 番目に頂点番号が大きいものを出力する。ただし、頂点 $ v $ と連結な頂点が $ k $ 個未満のときは `-1` を出力する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ ただし、$ \mathrm{query}_i $ は $ i $ 個目のクエリであり、以下のいずれかの形式で与えられる。 > $ 1 $ $ u $ $ v $ > $ 2 $ $ v $ $ k $

タイプ $ 2 $ のクエリの個数を $ q $ として、$ q $ 行出力せよ。$ i $ 行目には $ i $ 個目のタイプ $ 2 $ に対するクエリの答えを出力せよ。

### 制約 - $ 1\leq\ N,Q\leq\ 2\times\ 10^5 $ - タイプ $ 1 $ のクエリにおいて、$ 1\leq\ u\lt\ v\leq\ N $ - タイプ $ 2 $ のクエリにおいて、$ 1\leq\ v\leq\ N,\ 1\leq\ k\leq\ 10 $ - 入力は全て整数 ### Sample Explanation 1 \- $ 1 $ 個目のクエリについて、頂点 $ 1 $ と頂点 $ 2 $ の間に辺が追加されます。 - $ 2 $ 個目のクエリについて、頂点 $ 1 $ と連結な頂点は $ 1,2 $ の $ 2 $ つです。この中で $ 1 $ 番目に大きい $ 2 $ を出力します。 - $ 3 $ 個目のクエリについて、頂点 $ 1 $ と連結な頂点は $ 1,2 $ の $ 2 $ つです。この中で $ 2 $ 番目に大きい $ 1 $ を出力します。 - $ 4 $ 個目のクエリについて、頂点 $ 1 $ と連結な頂点は $ 1,2 $ の $ 2 $ つです。$ 3 $ 個未満なので `-1` を出力します。 - $ 5 $ 個目のクエリについて、頂点 $ 1 $ と頂点 $ 3 $ の間に辺が追加されます。 - $ 6 $ 個目のクエリについて、頂点 $ 2 $ と頂点 $ 3 $ の間に辺が追加されます。 - $ 7 $ 個目のクエリについて、頂点 $ 3 $ と頂点 $ 4 $ の間に辺が追加されます。 - $ 8 $ 個目のクエリについて、頂点 $ 1 $ と連結な頂点は $ 1,2,3,4 $ の $ 4 $ つです。この中で $ 1 $ 番目に大きい $ 4 $ を出力します。 - $ 9 $ 個目のクエリについて、頂点 $ 1 $ と連結な頂点は $ 1,2,3,4 $ の $ 4 $ つです。この中で $ 3 $ 番目に大きい $ 2 $ を出力します。 - $ 10 $ 個目のクエリについて、頂点 $ 1 $ と連結な頂点は $ 1,2,3,4 $ の $ 4 $ つです。$ 5 $ 個未満なので `-1` を出力します。